== include(page="template/taskheader" task_id="grau") ==

Fane a ales sa devina un magnat al graului dar acum are probleme mari din cauza normelor europene. Conform standardelor UE, fiecare tip de sol este caracterizat de doua proprietati, pH si indicele Feng shui, iar un agricultor poate cultiva grau decat pe tipuri de sol cu pH si indice Feng shui fixate. Din fericire, asupra oricarui tip de sol se pot executa mai multe operatii, fiecare operatie costand un leu iar efectul ei fiind modificarea cu o unitate a uneia din cele doua proprietati.
Fane a aflat care sunt cele $N$ tipuri de soluri acceptate de UE asa ca el isi analizeaza parcelele de pamant si vrea sa stie pentru fiecare care este costul minim prin care pot devenii soluri aprobate.

Fane a ales sa devina un magnat al graului dar acum are probleme mari din cauza normelor europene. Conform standardelor UE, fiecare tip de sol este caracterizat de doua proprietati, pH-ul si indicele Feng shui, iar un agricultor poate cultiva grau decat pe tipuri de sol cu pH si indice Feng shui fixate. Din fericire, asupra oricarui tip de sol se pot executa mai multe operatii, fiecare operatie costand un leu iar efectul ei fiind modificarea cu o unitate a uneia din cele doua proprietati.
Fane a aflat care sunt cele $N$ tipuri de soluri acceptate de UE asa ca el vrea sa stie pentru fiecare tip de sol pe care urmeaza sa cultive grau care este costul minim prin care poate devenii un sol aprobat.

Din pacate, Fane traieste in Romania, si aici multe din normele europene au fost introduse prost asa ca legislatia se modifica destul de des prin operatii de tipul: aprobarea tuturor solurilor cu anumite proprietati sau interzicerea solurilor de un anumit tip.
Cum intrebarile lui Fane pot fi precedate de schimbari de legislatie, aflati raspunsurile la ele in momentele respective.

* $1 ≤ N, M ≤ 250.000$
* Pot sa existe in orice moment mai multe legi care sa aprobe acelasi tip de sol, acestea fiind toate interzise in cazul unei operatii de tip 2.

* Toate numerele din fisierul de intrare sunt mai mici ca 2^28^ in valoare absoluta.

* Toate numerele din fisierul de intrare sunt intregi mai mici ca 2^28^ in valoare absoluta.

h2. Exemplu