O suprafata de pamant este impartita in NxM parcele de teren. Pe aceasta suprafata au fost plantati pe parcele de coordonate cunoscute un numar P de copaci, fiecare intr-un anumit an calendaristic. Astfel pentru un copac se cunosc valorile (Ai, Xi, Yi), cu 1 <= i <= P, unde Ai este anul in care a fost plantat copacul i iar Xi si Yi sunt coordonatele parcelei pe care a fost plantat. Se stie ca fiecare copac isi mareste inaltimea de K ori in fiecare an. Astfel, in anul in care a fost plantat, copacul are inaltimea 1, iar in al doilea an k, in al treilea k^2^ etc.
Definim o regiune ca fiind o suprafata de teren dreptunghiulara cu laturile paralele cu cele ale terenului, specificata prin parcelele stanga-sus si dreapta-jos: (XS, YS), (XD, YD).

O regiune este considerata "frumoasa", daca pentru fiecare inlatime H exista un numar par de copaci cu acea inaltime.

O regiune este considerata "frumoasa", daca pentru fiecare inaltime H exista un numar par de copaci cu acea inaltime.

In anul curent, 2015, proprietarul terenului este interesat pe rand de Q regiuni ale suprafetei. El doreste ca fiecare din aceste regiuni sa fie "frumoasa" la momentul respectiv. Proprietarul poate planta copaci insa **doar pe parcela din dreapta jos** a regiunii si va planta un numar minim de copaci. Dupa ce regiunea a devenit frumoasa, copacii plantati raman pe parcela respectiva si inaltimea lor ramane constanta. Apoi proprietarul este interesat de alta parcela pe care trebuie, eventual, plantati copaci ca acea parcela sa devina "frumoasa" la acel moment.

In anul 2015 proprietarul a descoperit o metoda ingenioasa a aduga noi copaci de orice inaltime. Folosind aceasta metoda el este interesat sa "infrumuseteze" pe rand Q regiuni ale suprafetei, pe parcursul anului. Copacii pot fi adaugati insa **doar pe parcela din dreapta jos** a regiunilor de interes si se vor planta un numar minim de copaci. Dupa ce regiunea a devenit frumoasa, copacii plantati raman pe parcela respectiva.

h2. Date de intrare