== include(page="template/taskheader" task_id="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. 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 inaltime $H$ exista un numar par de copaci cu acea inaltime.

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 inaltime H exista un numar par de copaci cu acea inaltime.

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

In anul 2015 proprietarul a descoperit o metoda ingenioasa a adauga 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

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 numerele $N$, $M$ si $K$, reprezentand dimensiunea terenului si 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 trei numere intregi: $Ai$ $Xi$ $Yi$.
Pe urmatoarea linie se afla numarul $Q$, reprezentand numarul de query-uri. Pe fiecare dintre cele $Q$ linii se afla patru numere intregi, reprezentand colturile din stanga sus si dreapta jos ale unei regiuni pe care proprietarul doreste sa o "infrumuseteze".

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 numerele N, M si K, reprezentand dimensiunea terenului si 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.
Pe urmatoarea linie se afla un numarul Q, reprezentand numarul de query-uri. Pe fiecare dintre cele Q linii se afla 4 numere intregi, reprezentand colturile din stanga sus si dreapta jos ale unei regiuni pe care proprietarul doreste sa o "infrumuseteze".

h2. Date de ieşire

Fişierul de ieşire $parcele2.out$ contine pentru fiecare test $Qi$ linii, 1≤i≤T. Pe fiecare linie, afisati un numar $C$, reprezentand numarul de copaci ce trebuie plantati de proprietar, urmat de o succesiune de inaltimi $H$, cu semnificatia ca acesta planteaza cate un copac de fiecare inaltime specificata. Pentru ca acestea pot fi numere foarte mari, afisati-le modulo $666013$. Inaltimile pot fi afisate in orice ordine.

Fişierul de ieşire $parcele2.out$ contine pentru fiecare test i, Qi linii, 1≤i≤T. Pe fiecare linie, afisati un numar C, reprezentand numarul de copaci ce trebuie plantati de proprietar, urmat de o succesiune de inaltimi H, cu semnificatia ca acesta planteaza cate un copac de fiecare inaltime specificata. Pentru ca acestea pot fi numere foarte mari, afisati-le modulo 666013. Inaltimile pot fi afisate in orice ordine.

h2. Restricţii