== include(page="template/taskheader" task_id="sir8") ==
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ă parola 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.
- 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.
h2.Cerinta
h2. Cerinta
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.
h2. Date de intrare
Pe prima linie a fişierului $sir8.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 ^ a$ (unde operatorul $^$ 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 ^ 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 ^ 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 ^ a$ (unde operatorul $^$ 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 ^ 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 ^ a$.
- $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 ^ a$ (unde operatorul $^$ reprezinta sau exclusiv – $xor$ ). Dacă rezultatul ultimei peraţii de tip Query a fost $1$, atunci poziţia pe care se inserează caracterul va fi calculată prin formula: $poz ^ 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 ^ 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 ^ a$ (unde operatorul $^$ 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 ^ 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 ^ a$.
h2. Date de ieşire
