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. (In primul an, anul in care a fost plantat, copacul are inaltimea 1, in al doilea an, k, in al treilea k^2 samd)
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.

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.

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

h2. Date de intrare