mindist

Se adaugă, pe rând, în plan, $N$ puncte. Fiecare punct are coordonatele întregi.
Pentru fiecare punct adăugat trebuie să găsiți distanța Manhattan minimă de la acel punct la oricare dintre punctele adăugate înaintea lui.

Date de intrare

Pe prima linie a fisierului de intrare mindist.in se va afla $N$, numărul de puncte.
Urmează $N$ linii, pe linia $i$ se vor afla coordonatele întregi $x_i \ y_i$ ale celui de-al $i$-lea punct inserat.

Date de ieșire

Fișierul de ieșire mindist.out va conține $N$ linii.
Pe linia $i$ se va afla un singur număr întreg, $d_i$, care reprezintă distanța Manhattan minimă de la punctul $i$ la oricare dintre punctele adăugate înaintea lui.

Restricții și precizări

• Răspunsul pentru punctul primul punct, $d_1$, se consideră a fi $0$
• Distanța Manhattan intre punctele $(x_1, y_1)$ și $(x_2, y_2)$ este definită ca $|x_1 - x_2| + |y_1 - y_2|$
• Pentru $20\%$ dintre teste, $N \leq 150$
• Pentru restul de $80\%$ dintre teste, $N \leq 50 \ 000$
• $1 \leq x_i, y_i \leq 50 \ 000$

Exemplu

mindist.in

4
4 1
3 4
2 2
1 3

mindist.out

0
4
3
2