Heroes

Time limit: 2s Memory limit: 512MB Input: Output:

Laserul protozoic getodacic carpatin ar învinge cu siguranță câmpul positronic de particule gamma qin al samurailor.
-- OTV

După ce ți-ai reparat mașina timpului, ai decis că prima oprire ar trebui să fie Dacia, tărâmul vestit și sacru al strămoșilor daci. Odată ce ai ieșit din mașină după introducerea coordonatelor, observi că ai ajuns în Piața Mare a fostei capitale Sarmizegetusa de ziua tuturor sfinților daci. Conform cunoștințelor tale, de această sărbătoare mereu este performat vestitul Dans al Dacului. Fiind prezent la o performanță a acestuia, ai dedus că acesta funcționează în felul următor:

Se adună NN eroi într-un cerc, fiecare având un număr de la 1 la NN inscripționat în fruntea lui. Inițial, aceste numere ale acestora sunt în ordine (vezi Restricții și Precizări). Apoi, se vor performa o serie de pași de dans conform șirului sacru a0,a1,,aK1a_0, a_1, \dots ,a_{K-1}, eroul cu numărul inscripționat 11 ținând o ștafetă.

La pasul xx se vor întâmpla în ordine următoarele:

  • Se notează cu i=(x mod K)i = (x \textrm{ mod } K), adică restul împărțirii lui xx la KK.
  • De aia_i ori se va întâmpla următorul lucru: eroul care tine ștafeta o va da persoanei care se află la dreapta si va iesi din cerc pentru a fi sacrificat lui Zalmoxis. Daca e un singur erou ramas la acest pas, acesta isi va preda simbolic lui insusi stafeta apoi va iesi si el din cerc. Daca acest procedeu nu se poate repeta de aia_i ori pentru ca au plecat toti eroii, dansul se va termina aici.
  • După eliminarea unui erou sacrificat, cercul se rearanjează astfel încât toți eroii rămași să formeze un nou cerc compact. Eroii rămași își păstrează ordinea inițială relativă între ei.
  • Apoi, de aia_i ori se va preda ștafeta la dreapta fără ca eroii să iasă din cerc.
  • Pasarea ștafetei continuă în următorul pas.

Este bine știut că dacii au fost fondatorii programării moderne, astfel, ei începeau mereu acest dans de la pasul 00.

După ce ai văzut această performanță incredibilă, te-ai gândit să întrebi un sătean de lângă tine câteva întrebări legate de dans, acestea venind în două varietăți:

  1. Al câtelea este eliminat omul cu ID-ul PP
  2. Care este ID-ul celui de-al PP-lea om eliminat

Cerință

După ce i-ai pus întrebările săteanului, acesta ți-a răspuns într-un singur cuvânt din daca veche, care preconizezi că ți-ar fi putut răspunde la toate întrebările. Cu toate acestea, nu ai urechea formată pentru a înțelege acest limbaj al zeilor, așa că ai rămas să te întrebi singur care ar putea fi răspunsul la aceste întrebări.

Date de intrare

Pe prima linie se află numerele naturale NN și KK, reprezentând numărul de eroi din cercul inițial și lungimea șirului sacru.

Pe a doua linie se află KK numere naturale a0,a1,a2,,aK1a_0, a_1, a_2, \dots, a_{K-1}, elementele șirului sacru.

Pe a treia linie se află numărul natural QQ, numărul de întrebări pe care le pui.

Pe următoarele QQ linii se află componentele întrebărilor. Astfel, fiecare linie se vor găsi două numere naturale TT și PP, reprezentând tipul întrebării și parametrul acesteia.

Date de ieșire

Pe cele QQ linii se vor afla răspunsurile la întrebări în ordine.

Restricții și precizări

  • Notă: La această problemă este atașat un videoclip care ilustrează ce se întâmplă în exemplul de mai jos.
  • 1N1091 \le N \le 10^9;
  • 1K1051 \le K \le 10^5;
  • 1Q1051 \le Q \le 10^5;
  • 1ai,PN1 \le a_i, P \le N, pentru 0i<K0 \le i < K;
  • 1T21 \le T \le 2;
  • Ordinea inițial este definită astfel:
    • Vecinul de la stânga al celui care are numărul ii inscripționat este cel cu numărul i1i - 1, iar cel de la dreapta este cel cu numărul i+1i + 1 pentru 2iN12 \le i \le N - 1.
    • Vecinul de la stânga al celui care are numărul 11 inscripționat este cel cu numărul NN, iar cel de la dreapta este cel cu numărul 22.
    • Vecinul de la stânga al celui care are numărul NN inscripționat este cel cu numărul N1N - 1, iar cel de la dreapta este cel cu numărul 11.
# Punctaj Restricții
1 2 N20N \le 20
2 3 N103N \le 10^3
3 10 N106N \le 10^6
4 14 K=1K = 1, a0=1a_0 = 1 și T=1T = 1 pentru orice întrebare
5 16 K=1K = 1, a0=1a_0 = 1 și T=2T = 2 pentru orice întrebare
6 18 T=1T = 1 pentru orice întrebare
7 20 T=2T = 2 pentru orice întrebare
8 17 Fără constrângeri suplimentare

Exemplu

stdin

12 2  
2 1  
12  
1 1  
1 2  
1 3  
1 4  
1 5  
1 6  
1 7  
1 8  
1 9  
1 10  
1 11  
1 12

stdout

1  
2  
7  
8  
3  
10  
4  
5  
11  
9  
6  
12

Explicație

Primul erou este eliminat primul, al doilea erou este eliminat al doilea, al treilea erou este eliminat al șaptelea, al patrulea erou este eliminat al optulea, al cincilea erou este eliminat al zecelea, al șaselea erou este eliminat al patrulea, al șaptelea erou este eliminat al cincilea, al optulea erou este eliminat al unsprezecelea, iar al nouălea erou este eliminat al nouălea. Ș.a.m.d.

Log in or sign up to be able to send submissions!