gate

Time limit: 0.25s Memory limit: 64MB Input: gate.in Output: gate.out

După ce a ajutat la conectarea oraşelor Nordemos şi Suderim, Negrimon s-a hotărât să-şi urmeze destinul şi să devină un programamon roşu. Pentru a-şi începe călătoria, este nevoit să părăsească Udobje Lurrak şi să treacă prin Sha’ar Azih, poarta magică de la ieşirea din oraşul Estumar. Această poartă se bazează pe un sistem de runix-uri aşezate în linie, numerotate de la 11 la NN. Un runix este un pătrat pe care este înscrisă o literă mică, din mulţimea unui alfabet restrâns, format din primele LL litere ale alfabetului englez. Alfabetul restrâns este circular, astfel încât după ultima literă urmează prima, iar înainte de prima literă este ultima literă din alfabet. În starea iniţială a sistemului, primul runix este setat pe litera aa, al doilea runix este setat pe următoarea literă din alfabetul restrâns ş.a.m.d.

De exemplu, pentru N=8N = 8 şi L=3L = 3, sistemul are configuraţia iniţială: abcabcab

  • pentru N=11N = 11 şi L=4L = 4, sistemul are configuraţia iniţială: abcdabcdabc
  • pentru N=14N = 14 şi L=7L = 7, sistemul are configuraţia iniţială: abcdefgabcdefg

Când Negrimon ajunge la poartă, aceasta prinde viaţă şi se produce un şir de acţiuni de următorul tip:

  1. Runix-ul cu numărul rr împreună cu toate runix-urile din stânga se deplasează şi se separă de cele din dreapta (dacă există), formându-se astfel două grupuri independente (iniţial toate runix-urile formează un singur grup).
  2. Toate runix-urile din grupul din care face parte runix-ul cu numărul rr execută o schimbare de pas pp. Aceasta constă în înlocuirea literei asociate cu următoarea a pp-a literă din alfabet (p>0p > 0) sau cu precedenta a (p)(-p)-a literă din alfabet (p<0p < 0). Datorită circularităţii alfabetului, oricât de mare ar fi pp va exista o literă care să fie la distanţa pp faţă de litera actuală.
  3. Negrimon primeşte o întrebare de tipul: pe ce literă este setat runix-ul cu numărul rr?

Poarta se deschide dacă Negrimon răspunde corect la toate întrebările primite şi astfel își poate continua călătoria în Azih Lurrak.

Cerinţă

Ajutaţi-l pe Negrimon să deschidă poarta.

Date de intrare

Pe prima linie a fişierului gate.in se află valorile NN, LL, MM, separate prin câte un spaţiu, cu semnificația: NN - numărul de runix-uri din sistem, LL - numărul de litere din alfabetul restrâns, MM - numărul de acţiuni desfăşurate. Fiecare dintre următoarele MM linii conţine valorile tt - tipul acţiunii, rr - numărul runix-ului la care se face referire, pp – schimbarea de pas a runix-ului, dacă acţiunea este una de tipul 2 (t=2t = 2), toate separate prin câte un spaţiu.

Date de ieșire

În fişierul gate.out se vor afla răspunsurile la întrebările primite, în ordinea în care sunt adresate. Fiecare răspuns ocupă olinie și este format dintr-un singur caracter ce reprezintă litera pe care este setat runix-ul cu numărul dat în întrebare.

Restricţii şi precizări

  • 1N,M200 0001 \leq N, M \leq 200 \ 000
  • 1rN1 \leq r \leq N
  • 100 000p100 000,p0-100 \ 000 \leq p \leq 100 \ 000, p \neq 0
  • Pentru teste în valoare de 20 de puncte, NM25 000 000N \cdot M \leq 25 \ 000 \ 000

Exemplu

gate.in

8 3 8
1 3
2 4 1
3 8
1 5
2 2 2
3 1
2 5 -1
3 5

gate.out

c
c
b

Explicație

Starea iniţială a sistemului: abcabcab\text{abcabcab}

  1. 1 3abc abcab\text{ab\underline{c}\ abcab}
  2. 2 4 1abc bcabc\text{abc\ \underline{b}cabc}
  3. 3 8abc bcabc\text{abc\ bcab\underline{c}}
  4. 1 5abc bc abc\text{abc\ b\underline{c}\ abc}
  5. 2 2 2cab bc abc\text{c\underline{a}b\ bc\ abc}
  6. 3 1cab bc abc\text{\underline{c}ab\ bc\ abc}
  7. 2 5 -1cab ab abc\text{cab\ a\underline{b}\ abc}
  8. 3 5cab ab abc\text{cab\ a\underline{b}\ abc}

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