distanceSumD

DistanceSum

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

Poveste şi cerinţă...

Se dau $N$ puncte în plan şi $M$ întrebări de forma: "care este suma distanţelor de la fiecare din cele $N$ puncte la punctul $(x, y)$ dat?".
Distanţa dintre doua puncte $(x{~1~}, y{~1~})$ şi $(x{~2~}, y{~2~})$ este $max(|x{~2~} - x{~1~}|, |y{~2~} - y{~1~}|)$.

h2. Date de intrare

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

Fişierul de intrare $distancesum.in$ conţine pe prima linie numerele $N$ şi $M$. Pe următoarele $N$ linii se găsesc numerele $x{~i~}$ şi $y{~i~}$ reprezentând coordonatele celor $N$ puncte din plan. Pe următoarele $M$ linii se găsesc numerele $x{~i~}$ şi $y{~i~}$ semnificând coordonatele punctelor din întrebări.

h2. Date de ieşire

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

În fişierul de ieşire $distancesum.out$ veţi afişa $M$ numere, câte unul pe linie, reprezentând răspunsurile la întrebări.

h2. Restricţii

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

* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 100.000$
* Toate coordonatele sunt numere întregi cuprinse între $-10^9^$ şi $10^9^$

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

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

| 4 3
3 5
-3 -2
1 4
-4 -3
2 -4
1 4
4 2
| 28
15
21

|

h3. Explicaţie
 
...
 

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