Intr-un sat, harta este un sistem de coordonate in care antena de telefonie se afla in originea O(0, 0), iar fiecare dintre cele n case are coordonate intregi. Antena poate functiona pe m niveluri de putere; la fiecare nivel ea acopera toate casele aflate la o distanta mai mica sau egala cu o anumita raza (casele aflate exact la distanta egala cu raza sunt acoperite).
Pentru fiecare nivel de putere, determinati cate case sunt acoperite de antena.
- Date de intrare
- Pe prima linie se afla n. Pe fiecare dintre urmatoarele n linii se afla coordonatele x si y ale unei case. Pe linia urmatoare se afla m, iar pe ultima linie cele m raze corespunzatoare nivelurilor de putere.
- Date de iesire
- Se afiseaza pe o singura linie m numere separate prin cate un spatiu: numarul de case acoperite pentru fiecare raza, in ordinea citirii.
- Restrictii
- 1 <= n, m <= 200 000 -1 000 000 <= x, y <= 1 000 000 1 <= raza <= 1 000 000 000
Exemple
Exemplul 1
Intrare
6 3 4 0 6 -1 -1 5 0 -6 8 2 -3 5 5 1 10 3 6
Iesire
4 0 6 1 5
Exemplul 2
Intrare
1 0 0 1 1
Iesire
1