点的移动

题目描述

平面上有 $N$ 个整数坐标点。如果将点 $(x_0,y_0)$ 移动到 $(x_1,y_1)$,则需要的代价为 $|x_0-x_1|+|y_0-y_1|$。求使得 $K(K=1, \cdots ,N)$ 个点在同一位置上最少需要的代价。

输入输出格式

输入格式


第一行一个正整数 $N$; 接下来 $N$ 行,每行两个正整数 $x_i$ 和 $y_i$,为第 $i$ 个点的坐标,不超过 $10^6$。 【数据规模】。 对于 $100\%$ 的数据中,满足 $1 \le N \le 50$。

输出格式


输出共 $N$ 行,第 $i$ 行为使得有 $i$ 个点在统一位置的最少代价。

输入输出样例

输入样例 #1

4
15 14
15 16
14 15 
16 15

输出样例 #1

0
2
3
4