== include(page="template/taskheader" task_id="grau") ==
Se da o multime cu $N$ puncte in plan pe care se pot executa urmatoarele operatii:
0 (x,y) afla distanta minima manhattan de la punctul (x,y) la un punct din multime
1 (x,y) insereaza punctul (x,y) in multime
2 (x,y) sterge toate punctele de coordonate (x,y) din multime (se garanteaza ca exista)
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 doar 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.
h2. Date de intrare
Prima linie a fisierui de intrare contine numarul $N$ iar pe urmaroarele N linii de afla coordonatele punctelor. Linia $N+2$ contine numarul $M$ de operatii iar fiecare din urmatoarele $M$ linii contin care 3 numere care descriu operatile de mai sus.
Prima linie a fisierui de intrare contine numarul $N$ iar pe urmaroarele $N$ linii de afla cele doua proprietati ale solurilor. Linia $N+2$ contine numarul $M$ de operatii iar fiecare din urmatoarele $M$ linii contin care 3 numere, $op$, $X$, $Y$, care descriu operatile de mai sus astfel: $X$ si $Y$ descriu pH-ul respectiv indicele Feng shui al unui tip de sol iar valoarea lui $op$ este 0, in cazul unei intrebari puse de Fane, 1, in cazul in care trebuie introdusa o lege noua care sa aprobe tipul descris de sol sau 2 daca trebuie abrogata o lege.
h2. Date de iesire
Pentru fiecare operatie de tip 0, sa se gaseasca distanta minima manhattan de la punctul dat la un punct din multime.
Raspunsurile la intrebarile lui Fane se vor afla in fisierul de iesire, cate unul pe linie, in ordinea in care au fost date.
h2. Restrictii
* $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 intregi mai mici ca 2^28^ in valoare absoluta.
h2. Exemplu
table(example). |_. grau.in |_. grau.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
2 3
1 1
0 0
5 7
4
1 5 6
0 5 5
2 1 1
0 1 1
| 1
2
|
h3. Explicatie
...
Solul de tip (5, 5) poate fi transformat cu cost 1 intr-un sol de tip (5, 6) iar solul de tip (1, 1) este transformat intr-un sol de tip (0, 0) cu cost 2.
== include(page="template/taskfooter" task_id="grau") ==
