Fişierul intrare/ieşire:	moft.in, moft.out	Sursă	Marcel
Autor	Alexandru Petrescu	Adăugată de	Alexandru Petrescu •alexpetrescu
Timp execuţie pe test	0.2 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

Moft

Marcel se afla acum intr-un univers foarte abstract. Numerele capata sentiment, iar capriciile lor devin supradimensionate. Asa se face ca sunt S numere mofturoase, fie ele K_i, si un multiset de numere initial vid. Amintim faptul ca intr-un multiset un numar poate aparea de mai multe ori. Asupra multisetului se fac N operatii:

• 1 x : este inserat numarul x in multiset. Acestuia i se asociaza un numar id egal cu cel mai mic numar natural nenul care nu a mai fost asociat altui numar inainte.
• 2 id : este sters din multiset numarul caruia i-a fost asociat numarul id. Se garanteaza ca acesta se afla in multiset.

Dupa fiecare din aceste N operatii, fiecare din cele S numere mofturoase se intreaba care ar fi numarul de pe pozitia K_i daca am aranja crescator numerele din multiset.

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, care va fi afisat in output, care va fi egal cu (P₁ * 1) xor (P₂ * 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!

Date de intrare

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.

Date de ieşire

Î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.

Restricţii

• 1 ≤ H, K_i ≤ 1.000.000.000
• 1 ≤ T ≤ 3
• 1 ≤ N, S

Punctare

La evaluare vor fi folosite 20 de teste, fiecare valorand cate 5 puncte. Ele sunt organizate dupa cum urmeaza:

• 1 test: t = 0, N ≤ 1.000, S ≤ 1.000, nu exista operatii de tipul 2
• 1 test: t = 0, N ≤ 1.000, S ≤ 1.000
• 1 test: t = 0, N ≤ 30.000, S ≤ 1.000
• 1 test: t = 1, N ≤ 30.000, S ≤ 1.000, nu exista operatii de tipul 2
• 1 test: t = 1, N ≤ 30.000, S ≤ 1.000

• 1 test: t = 0, N ≤ 1.000.000, S = 1, nu exista operatii de tipul 2
• 1 test: t = 0, N ≤ 1.000.000, S = 1
• 2 teste: t = 1, N ≤ 1.000.000, S = 1, nu exista operatii de tipul 2
• 3 teste: t = 1, N ≤ 1.000.000, S = 1

• 1 test: t = 0, N ≤ 200.000, S ≤ 50, nu exista operatii de tipul 2
• 2 teste: t = 0, N ≤ 200.000, S ≤ 50
• 2 teste: t = 1, N ≤ 200.000, S ≤ 50, nu exista operatii de tipul 2
• 3 teste: t = 1, N ≤ 200.000, S ≤ 50

Exemplu

Explicaţie

...

Cum se trimit solutii?