== 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 inlatime H exista un numar par de copaci cu acea inaltime.
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.
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 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.
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 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>.
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".
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".
h2. Date de ieşire
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.
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.
h2. Restricţii
* 1 ≤ T ≤ 10
* 1955 ≤ Ai ≤ 2015
* 1 ≤ N, M ≤ 2000, dimensiunele terenului
* 1 ≤ N, M ≤ 1000
* 1 ≤ Xi ≤ N si 1 ≤ Yi ≤ M
* 1 ≤ K ≤ 100
* 1 ≤ P + Q ≤ 1000
* 1 ≤ T ≤ 10
* Anul curent este 2015.
* 1 ≤ P + Q ≤ 2000
h2. Exemplu
La inceput sunt patru copaci plantati pe teren ca in figura alaturata:
{! problema/parcele2?parcele1.jpg 54% !}
Proprietarul doreste sa afle ce copaci trebuie sa mai planteze pe regiunea ((1, 1)(2, 3)) pentru ca aceasta sa devina frumoasa. El planteaza astfel un copac de inaltime 81 si unul de inaltime 3 pe parcele (2, 3).
Proprietarul doreste sa afle ce copaci trebuie sa mai planteze pe regiunea ((1,1) (2,3)) pentru ca aceasta sa devina frumoasa. El planteaza astfel un copac de inaltime 81 si unul de inaltime 3 pe parcele (2,3).
{! problema/parcele2?parcele2.jpg 54% !}
Apoi, acesta doreste sa "infrumuseteze" regiunea ((2, 2)(3, 4)) si va planta un copac pe parcela (3, 4), de inaltime 3.
Apoi, acesta doreste sa "infrumuseteze" regiunea ((2,2) (3,4)) si va planta un copac pe parcela (3,4), de inaltime 3.
{! problema/parcele2?parcele3.jpg 54% !}
In final, pentru a "infrumuseta" regiunea ((1, 2)(2, 4)), el nu trebuie sa planteze niciun copac.
In final, pentru a "infrumuseta" regiunea ((1,2) (2,4)), el nu trebuie sa planteze niciun copac.
{! problema/parcele2?parcele4.jpg 54% !}
== include(page="template/taskfooter" task_id="parcele2") ==
