Fişierul intrare/ieşire:	parcele2.in, parcele2.out	Sursă	ONIS 2015, Runda 3
Autor	Alexandru Ionita	Adăugată de	Paul Diac •diac_paul
Timp execuţie pe test	0.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Parcele2

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

Date de intrare

Pe prima linie a fisierului de intrare parcele2.in se va afla T, reprezentand numarul de teste. In cadrul unui test, pe prima linie se vor afisa nr N M si K, reprezentand dimensiunea terenului si K, coeficientul de crestere a copacilor intr-un an. Pe urmatoarea linie urmeaza numarul P, reprezentand numarul de copaci plantati initial pe parcela. Pe fiecare dintre urmatoarele P linii se afla 3 numere intregi: <Ai, Xi, Yi> Ai, anul in care a fost plantat copacul i, respectiv Xi si Yi, coordonatele parcelei pe care a fost plantat.
Pe urmatoarea linie se afla un nr Q, reprezentand nr de query-uri. Pe fiecare dintre cele Q linii se afla 4 nr intregi, reprezentand colturile din stanga sus si dreapta jos ale unei regiuni pe care proprietarul doreste sa o "infrumuseteze".

Date de ieşire

Fişierul de ieşire parcele2.out contie Qi linii, 1<=i<=T. Pe fiecare linie, afisati o succesiune de inaltimi H, cu semnificatia ca proprietarul planteaza cate un copac de fiecare inlatime specificata. Daca nu trebuie plantat niciun copac, pentru o anumita regiune, afisati pe linia respectiva "Nu trebuie plantati copaci". (Pt ca acestea pot fi numere foarte mari, afisati-le modulo 666013). La sfarsitul fiecarui query se considera ca se raman plantati acei copai, asadar vor fi luati in considerare in urmatoarele query-uri.

Restricţii

• 1955 ≤ Ai ≤ 2015
• 1 ≤ N, M ≤ 2000, dimensiunele terenului
• 1 ≤ Xi ≤ N si 1 ≤ Yi ≤ M
• 1 ≤ K ≤ 100
• 1 ≤ P + Q ≤ 1000
• 1 ≤ T ≤ 10
• Anul curent este 2015.

Exemplu

Explicaţie

Cum se trimit solutii?