Grendizer

grendizer

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

Grendizer, robotul din serialul de desene animate urmărit de Algorel în prag de Stele, are o nouă armă. Această armă funcţionează în felul următor: Grendizer işi stabileşte un punct de detonare şi o rază de acţiune $K$; toate obiectivele aflate la distanţa Manhattan exact $K$ faţă vor fi lovite.
 
Algorel a inventariat cele N obiective pe care Grendizer le are de distrus într-unul din episoade. Acum îşi pune întrebări de genul: dacă Grendizer detonează arma în punctul (x, y) cu raza de actiune K, câte din obiective vor fi lovite?
 
Cred că deja ştiţi cine trebuie să rezolve problema în locul obraznicului Algorel - care nu mai ştie niciun algoritm de când cu desenele animate.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $grendizer.in$ conţine pe prima linie două numere naturale, N si M, reprezentând numarul de obiectiv respectiv numarul de intrebari pentru care Algorel vrea sa afle raspunsul. Urmeaza N linii ce contin cate doua numere intregi reprezentand coordonatele unui obiectiv. Urmatoarele M linii descriu cate o intrebare prin trei numere separate prin spatii: x y K avand semnificatia de mai sus.

Fişierul de intrare $grendizer.in$ ...

h2. Date de ieşire

În fişierul de ieşire $grendizer.out$ veti afisa M linii cu raspunsul pentru fiecare din cele M intrebari.

În fişierul de ieşire $grendizer.out$ ...

h2. Restricţii

* Obiectivele se pot suprapune
* Distanta Manahattan intre doua puncte $(x{~1~}, y{~1~})$ si $(x{~2~}, y{~2~})$ este $|x{~1~} - x{~2~}| + |y{~1~} - y{~2~}|$
* Urmatorul tabel specifică valorile pentru N, M si MAX_MOD (punctele vor avea coordonate in intervalul [-MAX_MOD, +MAX_MOD]) pentru fiecare din teste:
 
table(numbers). |_. Test | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|_. N | x | x | x | x | x | x | x | x | x | x |
|_. M | x | x | x | x | x | x | x | x | x | x |
|_. MAX_MOD | x | x | x | x | x | x | x | x | x | x |

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

h2. Exemplu