h2. Detalii tehnice

Pentru a nu supraincarca fisierul de iesire cu toate mofturile numerelor, si pentru a ne asigura ca numai solutiile cele mai deosebite vor fi punctate corespunzator, dupa fiecare operatie se calculeaza numarul $P$ ca fiind produsul raspunsurilor la cele $S$ intrebari, $modulo 1.000.000.007$. Daca intrebarea este invalida, adica $K{~i~} > $ numarul elementelor din multiset, $P$ nu se modifica (se simuleaza inmultirea cu elementul neutru, si anume $1$). In functie de el, se va stabili si numarul care urmeaza sa fie inserat sau sters, dupa cum urmeaza: Daca numarul din $input$ este $H$, valoarea utilizata este data de $H xor (P * t)$, iar $t$ este o valoare cunoscuta, egala fie cu $0$, fie cu $1$. Pentru prima operatie se va considera ca $P$ = 1. Valoarea lui $P$ nu trebuie afisata, ci folosita pentru calcularea raspunsului final, singurul numar din $output$, care va fi egal cu $(P{~1~} * 1) xor (P{~2~} * 2) xor ... xor (P{~N~} * N)$, unde cu $P{~i~}$ am notat valoarea lui $P$ dupa primele $i$ operatii. A se observa ca valoarea care trebuie afisata *nu* este calculata $modulo 1.000.000.007$!

Pentru a nu supraincarca fisierul de iesire cu toate mofturile numerelor, si pentru a ne asigura ca numai solutiile cele mai deosebite vor fi punctate corespunzator, dupa fiecare operatie se calculeaza numarul $P$ ca fiind produsul raspunsurilor la cele $S$ intrebari, $modulo 1.000.000.007$. Daca intrebarea este invalida, adica $K{~i~} > $ numarul elementelor din multiset, $P$ nu se modifica (se simuleaza inmultirea cu elementul neutru, si anume $1$). In functie de el, se va stabili si numarul care urmeaza sa fie inserat sau sters, dupa cum urmeaza: Daca numarul din $input$ este $H$, valoarea utilizata este data de $H xor (P * t)$, iar $t$ este o valoare cunoscuta, egala fie cu $0$, fie cu $1$. Pentru prima operatie se va considera ca $P$ = 1. Valoarea lui $P$ nu trebuie afisata, ci folosita pentru calcularea raspunsului final, care va fi afisat in $output$, care va fi egal cu $(P{~1~} * 1) xor (P{~2~} * 2) xor ... xor (P{~N~} * N)$, unde cu $P{~i~}$ am notat valoarea lui $P$ dupa primele $i$ operatii. A se observa ca valoarea care trebuie afisata *nu* este calculata $modulo 1.000.000.007$!

h2. Date de intrare

Fişierul de intrare $moft.in$ ...

Fişierul de intrare $moft.in$ contine pe prima linie numarul $t$, a carui utilitate a fost evidentiata mai sus, si numarul $T$ de teste. Structura fiecarui test e urmatoarea: Pe prima linie se afla numarul $S$, pe a doua cele $S$ numere $K{~i~}$, pe a treia numarul $N$ de operatii, iar pe urmatoarele N linii cate o pereche $u H$, unde $u$ este fie $1$, fie $2$, in functie de tipul operatiei, iar $H$ trebuie modificat dupa cum este explicat mai sus.

h2. Date de ieşire

În fişierul de ieşire $moft.out$ ...

În fişierul de ieşire $moft.out$ se afla, pentru fiecare din cele $T$ teste, cate un numar, reprezentand raspunsul final care este calculat dupa cum ati citit.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ H, K{~i~} ≤ 1.000.000.000$
* $1 ≤ T ≤ 3$
* $1 ≤ N, S$
 
h2. Punctare
 
La evaluare vor fi folosite 20 de teste, fiecare valorand cate 5 puncte. Ele sunt organizate dupa cum urmeaza:
 
* $2$ teste: $t = 0$, $N ≤ 1.000$, $S ≤ 1.000$
* $1$ test: $t = 0$, $N ≤ 10.000$, $S ≤ 1.000$
* $2$ teste: $t = 1$, $N ≤ 10.000$, $S ≤ 1.000$
 
* $2$ teste: $t = 0$, $N ≤ 1.000.000$, $S = 1$
* $5$ teste: $t = 1$, $N ≤ 1.000.000$, $S = 1$
 
* $3$ teste: $t = 0$, $N ≤ 200.000$, $S ≤ 50$
* $5$ teste: $t = 1$, $N ≤ 200.000$, $S ≤ 50$

h2. Exemplu