Fişierul intrare/ieşire:arcas.in, arcas.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 16
AutorChichirim GeorgeAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.7 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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

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.

Date de ieşire

În fişierul de ieşire arcas.out se va afisa raspunsul pentru fiecare intrebare pe cate o linie, mai exact cate tinte a nimerit Hercule la fircare tragere.

Restricţii

  • 1 ≤ N, M ≤ 105
  • 1 ≤ x, y1, y2 ≤ 105
  • 1 ≤ x, y, r ≤ 105
  • y1 ≤ y2

Exemplu

arcas.inarcas.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

Explicaţie

Tintele sunt colorate cu maro, iar traiectoria sagetii este colorata cu rosu

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?