arcas

Arcas

== include(page="template/taskheader" task_id="arcas") ==

Dupa ce Hercule si-a aratat maiestria cu sulita sa magica acesta a observat ca nu mai impresioneaza doamnele ca in vremurile bune, asa ca s-a hotarat sa invete sa traga cu arcul. Ca sa poata cucerii din nou ca alta data Hercule s-a hotarat sa traga cu arcul din mai multe pozitii din plan, cu varful sagetii la 45 de grade si sa-si foloseasca vestitele puteri pentru a face sageata ca si disparuta dupa un anumit timp. Mai exact, in plan se afla N tinte verticale reprezentate prin $x$, $y1$ si $y2$ cu semnificatia ca tinta se afla de la poztia $(x,y1)$ la pozitia $(x,y2)$ in plan. Acesta trage de M ori cu arcul din diferite pozitii reprzentate de perechea de coordonate $(x,y)$ si cu puterea $r$, care semnifica faptul ca dupa ce sageata a trecut prin punctele $(x,y), (x+1,y+1), (x+2,y+2),..., (x+r,y+r)$ acesta isi foloseste puterile si o face ca si disparuta. Datoria voastra e sa-l ajutati pe Hercule sa impresioneze toate domnitile spunandu-i cate tinte a nimerit (o tinta este nimerita daca sageata trece prin ea, inclusiv prin capetele acesteia).

 
Dupa ce Hercule si-a aratat maiestria cu sulita sa magica acesta a observat ca nu mai impresioneaza doamnele ca in vremurile bune, asa ca s-a hotarat sa invete sa traga cu arcul. Ca sa poata cuceri din nou ca alta data Hercule s-a hotarat sa traga cu arcul din mai multe pozitii din plan, cu varful sagetii la 45 de grade si sa-si foloseasca vestitele puteri pentru a face sageata ca si disparuta dupa un anumit timp. Mai exact, in plan se afla $N$ tinte verticale reprezentate prin $x$, $y1$ si $y2$ cu semnificatia ca tinta se afla de la poztia $(x,y1)$ la pozitia $(x,y2)$ in plan. Acesta trage de $M$ ori cu arcul din diferite pozitii reprezentate de perechea de coordonate $(x,y)$ si cu puterea $r$, care semnifica faptul ca dupa ce sageata a trecut prin punctele $(x,y), (x+1,y+1), (x+2,y+2),..., (x+r,y+r)$ acesta isi foloseste puterile si o face ca si disparuta. Datoria voastra e sa-l ajutati pe Hercule sa impresioneze toate domnitile spunandu-i cate tinte a nimerit (o tinta este nimerita daca sageata trece prin ea, inclusiv prin capetele acesteia).

h2. Date de intrare

Fişierul de intrare $arcas.in$ contine pe prima linie 2 numere naturale N (numarul de tinte) si M (numarul de trageri). Pe urmatoatele N linii se afla cate un triplet de numere naturale de forma $x y1 y2$ cu semnificatia ca se afla o tinta cu capetele in pozitiile $(x,y1)$ si $(x,y2)$. Pe urmatoarele N linii se afla cate un triplet de numere naturale de forma $x y r$ cu semnificatia ca Hercule trage cu arcul din punctul de coordonate $(x,y)$ si cu puterea $r$.

Fişierul de intrare $arcas.in$ contine pe prima linie doua numere naturale $N$ (numarul de tinte) si $M$ (numarul de trageri). Pe urmatoatele $N$ linii se afla cate un triplet de numere naturale de forma $x$ $y1$ $y2$ cu semnificatia ca se afla o tinta cu capetele in pozitiile $(x,y1)$ si $(x,y2)$. Pe urmatoarele $M$ linii se afla cate un triplet de numere naturale de forma $x$ $y$ $r$ cu semnificatia ca Hercule trage cu arcul din punctul de coordonate $(x,y)$ si cu puterea $r$.

h2. Date de ieşire

h2. Restricţii

* 1 &le; N, M &le; <tex>10^5</tex>
* 1 &le; x, y1, y2 &le; <tex>10^5</tex>
* 1 &le; x, y, r &le; <tex>10^5</tex>

* $1 ≤ N, M ≤ 10^5^$
* $1 ≤ x, y1, y2 ≤ 10^5^$
* $1 ≤ x, y, r ≤ 10^5^$
* **$y1 ≤ y2$**

h2. Exemplu

h3. Explicaţie

...

Tintele sunt colorate cu maro, iar traiectoria sagetii este colorata cu rosu
 
!problema/arcas?arcas.png!

== include(page="template/taskfooter" task_id="arcas") ==