Șir

S, fost olimpic la informatică, încearcă să prevină atacurile de securitate ce pot apărea în reţeaua lui. Astfel, el are un şir de caractere special, preferat de el ca şi parolă. Pentru a verifica dacă arola lui este suficient de puternică, acesta a creat o listă $L$ de dimensiune $K$ cu parolele preferate de hackeri. Preventiv din fire, acesta doreşte să facă asupra parolei următoarele operaţii:

• Insert, se insereaza o literă $C$ la o poziţie $X$. În acest caz, toate caracterele care au o poziţie mai mare sau egală cu $X$ se vor muta cu o poziţie la dreapta, iar pe poziţia $X$ va fi inserat caracterul $C$.
• Query, se întreabă dacă al $Y$-lea cuvânt din lista de parole coincide cu subsecvenţa de aceeaşi lungime care se termina pe pozitia $Z$ în şirul special. Ultimul caracter al celui de-al $Y$-lea cuvânt va trebui să coincidă cu caracterul de pe poziţia $Z$, penultimul caracter al celui de-al $Y$-lea cuvânt va trebui să coincidă cu caracterul de pe poziţia $Z-1$ ş.a.

Cerință

Cunoscându-se şirul de caractere special, $K$ – lungimea listei de cuvinte, cele $K$ cuvinte şi o succesiune de $Q$ operaţii, să se răspundă la operaţiile de tip Query.

Date de intrare

Pe prima linie a fişierului sir.in se află şirul special. Pe cea de-a doua linie se află $K$, lungimea listei de cuvinte. Pe următoarele $k$ linii se află parolele ce aparţin listei, câte una pe linie. Pe următoarea linie, se află $Q$, numărul de operaţii. Următoarele $Q$ linii descriu aceste operaţii. O linie descrie o operaţie astfel:

• 0 poz c a b - Primul număr, zero, reprezintă tipul operaţiei, respectiv insert. $C$ reprezintă caracterul care va fi inserat. Folosind $poz, a$ şi $b$, vom calcula poziţia pe care caracterul va fi inserat. Dacă rezultatul ultimei operaţii de tip Query a fost $0$, atunci poziţia pe care se inserează caracterul va fi calculată prin formula: $poz \oplus a$ (unde operatorul $\oplus$ reprezinta sau exclusiv – xor ). Dacă rezultatul ultimei operaţii de tip Query a fost $1$, atunci poziţia pe care se inserează caracterul va fi calculată prin formula: $poz \oplus b$. În caz că operaţia curentă nu a fost precedată de nicio operaţie de tip Query, atunci poziţia pe care se inserează caracterul va fi calculată prin formula: $poz \oplus a$.
• 1 poz ind a b - Primul număr, unu, reprezintă tipul operaţiei, respectiv query. Al treilea număr, $ind$, reprezintă indicele cuvântului din lista pe care vom efectua operaţia de tip query. Folosind $poz, a$ şi $b$, vom calcula poziţia pe care se termină al $ind$-lea cuvânt din lista de parole. Dacă rezultatul ultimei operaţii de tip Query a fost $0$, atunci poziţia pe care se inserează caracterul va fi calculată prin formula: $poz \oplus a$ (unde operatorul $\oplus$ reprezintăsau exclusiv – xor ). Dacă rezultatul ultimei operaţii de tip Query a fost $1$, atunci poziţia pe care se inserează caracterul va fi calculată prin formula: $poz \oplus b$. În caz că operaţia curentă nu a fost precedată de nicio operaţie de tip Query, atunci poziţia pe care se inserează caracterul va fi calculată prin formula: $poz \oplus a$.

Date de ieșire

Pentru fiecare operaţie de tip query, se va afişa $0$ în cazul în care cuvântul nu se potriveşte, respectiv $1$ în caz că se potriveşte.

Restricții și precizări

• Se garantează că suma lungimilor cuvintelor din dicţionar este mai mică decât $800 \ 000$
• Se garantează că lungimea maximă a şirului special nu depăşeşte $60 \ 000$ după ce s-au efectuat toate operaţiile Insert.
• Numărul de operaţii este mai mic sau egal cu $85 \ 000$.

Exemplu

sir.in

photoshop 
2 
hoto 
goto 
4 
1 14643 1 14646 27787 
0 88412 g 38665 88415 
1 41453 2 37823 41451 
1 78120 1 98233 78125

sir.out

1 
1 
0

Explicație

În urma operaţiei xor, fişierul se transformă în:

photoshop 
2 
hoto 
goto 
4 
1 5 1
0 3 g
1 6 2 
1 5 1