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 (x1,y1) şi (x2,y2) este (x1-x2)2+(y1-y2)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 puncte1.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 puncte1.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
1 ≤ N ≤ 100 000
1 ≤ M ≤ 200 000
Toate coordonatele din fişierul de intrare sunt numere naturale din intervalul [1,109]
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≥90000 şi M≥150000.
Exemple
puncte1.in
puncte1.out
Explicaţii
3 2
1 1
5 1
10 2
2
7
2
5
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)).
