Stelele Informaticii 2024 - Mirror Day 2 | Heroes

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ă $N$ eroi într-un cerc, fiecare având un număr de la 1 la $N$ 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 $a_0, a_1, \dots ,a_{K-1}$, eroul cu numărul inscripționat $1$ ținând o ștafetă.

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

• Se notează cu $i = (x \textrm{ mod } K)$, adică restul împărțirii lui $x$ la $K$.
• De $a_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 $a_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 $a_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 $0$.

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 $P$
2. Care este ID-ul celui de-al $P$-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 $N$ și $K$, reprezentând numărul de eroi din cercul inițial și lungimea șirului sacru.

Pe a doua linie se află $K$ numere naturale $a_0, a_1, a_2, \dots, a_{K-1}$, elementele șirului sacru.

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

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

Date de ieșire

Pe cele $Q$ 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.
• $1 \le N \le 10^9$;
• $1 \le K \le 10^5$;
• $1 \le Q \le 10^5$;
• $1 \le a_i, P \le N$, pentru $0 \le i < K$;
• $1 \le T \le 2$;
• Ordinea inițial este definită astfel:
  • Vecinul de la stânga al celui care are numărul $i$ inscripționat este cel cu numărul $i - 1$, iar cel de la dreapta este cel cu numărul $i + 1$ pentru $2 \le i \le N - 1$.
  • Vecinul de la stânga al celui care are numărul $1$ inscripționat este cel cu numărul $N$, iar cel de la dreapta este cel cu numărul $2$.
  • Vecinul de la stânga al celui care are numărul $N$ inscripționat este cel cu numărul $N - 1$, iar cel de la dreapta este cel cu numărul $1$.

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.