Problem 1855: puncte

Zăhărel a desenat pe o foaie de hârtie $N$ puncte în plan. Curios din fire, şi-a ales încă $M$ puncte pe axa OX şi s-a întrebat pentru fiecare dintre cele $M$ puncte de pe axa Ox care dintre cele $N$ puncte este cel mai apropiat (situat la distanţă minimă). Se consideră că distanţa dintre două puncte $(x_1, y_1)$ şi $(x_2, y_2)$ este $(x_1 - x_2)^2$ + $(y_1 - y_2)^2$ .

Cerinţă

Scrieţi un program pentru Zăhărel care să determine pentru fiecare dintre cele $M$ puncte de pe axa OX, care este distanţa la cel mai apropiat punct dintre cele $N$ desenate pe hârtie.

Date de intrare

Fişierul de intrare puncte.in conţine pe prima linie numerele naturale $N$ , $M$ separate prin spaţii. Fiecare dintre următoarele $N$ linii conţine câte o pereche de numere naturale nenule $x \ y$ , separate prin spaţii, reprezentând coordonatele celor $N$ puncte (în ordinea abscisă, ordonată). Fiecare dintre următoarele $M$ linii conţine câte un număr natural $x$ , reprezentând abscisele (coordonatele pe axa OX) ale celor $M$ puncte.

Date de ieşire

Fişierul de ieşire puncte.out va conţine $M$ linii. Pe linia $i$ va fi scris un număr natural reprezentând distanţa la cel mai apropiat punct dintre cele $N$ de pe hârtie pentru al $i$ -lea punct de pe axa OX (considerând ordinea punctelor din fişierul de intrare).

Restricții și precizări

$1 \leq N \leq 100 \ 000$
$1 \leq M \leq 200 \ 000$
Toate coordonatele din fişierul de intrare sunt numere naturale din intervalul $[1, 10^9]$
Cele $N$ puncte din fişierul de intrare sunt sortate după coordonata $x$ crescător, iar în cazul în care două puncte au aceeaşi abscisă, ele sunt ordonate crescător după coordonata $y$ .
Pentru $50\%$ din teste $N \geq 90 \ 000$ şi $M \geq 150 \ 000$ .

Exemplu

puncte.in

puncte.out

2 
5

Explicație

Pe hârtie au fost desenate $3$ puncte, având coordonatele $(1,1)$ , $(5,1)$ , respectiv $(10,2)$ . Pe axa OX se află $2$ puncte, având abscisa $2$ , respectiv $7$ .
Distanţa minimă dintre punctul de pe axa OX de abscisă $2$ este $2$ (cel mai apropiat punct fiind cel de coordonate $(1,1)$ ).
Distanţa minimă dintre punctul de pe axa OX de abscisă $7$ este $5$ (cel mai apropiat punct fiind cel de coordonate $(5,1)$ ).

puncte