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ța

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 puncte4.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 puncte4.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 ≤ N ≤ 100.000
• 1 ≤ M ≤ 200.000
• Toate coordonatele din fișierul de intrare sunt numere naturale din intervalul [1, 1.000.000.000]
• 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.

Exemplu:

puncte4.in

3 2
1 1 
5 1
10 2
2
7

puncte4.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)).