Description

There are $N$ points with integer coordinates on the plane. Moving point $(x_0, y_0)$ to $(x_1, y_1)$ costs $|x_0-x_1|+|y_0-y_1|$. For each $K$ ($K = 1, \cdots, N$), find the minimum total cost to make $K$ points coincide at the same position.

Input Format

The first line contains a positive integer $N$.

The next $N$ lines each contain two positive integers $x_i$ and $y_i$, the coordinates of the $i$-th point, each not exceeding $10^6$.

Constraints: For $100\%$ of the testdata, $1 \le N \le 50$.

Output Format

Output $N$ lines. The $i$-th line is the minimum total cost to make $i$ points coincide at the same position.

4
15 14
15 16
14 15 
16 15

0
2
3
4

Hint

Translated by ChatGPT 5