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

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.

h2. Date de intrare

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

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 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 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 ≤ N, M ≤ 10^5^$
* $1 ≤ x, y1, y2 ≤ 10^5^$
* $1 ≤ x, y, r ≤ 10^5^$
* **$y1 ≤ y2$**

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. arcas.in |_. arcas.out |

| 4 3
  2 3 6
  4 1 3
  7 4 7
  9 2 6
  1 2 4
  2 1 6
  7 2 2
| 1
  2
  1

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
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") ==