题目描述

平面上分布了 $N$ 个点，每个点的坐标都是一个整数。假设将一个点 $(x_1, y_1)$ 移动到另一个点 $(x_2, y_2)$ 的代价为两点之间的曼哈顿距离，也就是最小代价为 $|x_1-x_2|+|y_1-y_2|$。

请求出，从平面中给定的点中，任意取出 $K$（$K=1,2,\dots,N$）个点，这 $K$ 个点移动到同一个点上最小总代价是多少？

输入格式

• 第一行一个正整数 $N$；
• 接下来 $N$ 行，每行两个正整数 $x_i$ 和 $y_i$，为第 $i$ 个点的坐标。

输出格式

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

样例

3
1 2
5 6
3 4

0
4
8

4
15 14
15 16
14 15
16 15

0
2
3
4

15
1 6
2 4
2 10
12 14
9 14
13 90
25 31
9 9
7 30
7 13
0 4
14 10
10 5
1 34
3 36

0
2
4
11
19
28
35
47
60
75
95
125
155
194
277

提示

• 从 $3$ 个点中选 $1$ 个点，移到同一个点的最小代价是 $0$，只有 $1$ 个点不需要移动；
• 从 $3$ 个点中选 $2$ 个点，移到同一个点的最小代价是 $4$，可以将 $(1,2)$ 点移动到 $(3,4)$ 点；
• 从 $3$ 个点中选 $3$ 个点，移动到同一个点的最小代价是 $8$，可以将 $(1,2)$ 点移动到 $(3,4)$ 点，代价是 $4$；再将 $(5,6)$ 点也移动到 $(3,4)$ 点，代价也是 $4$，因此最小代价是 $8$。

数据范围

• $1 \le N \le 50$
• 每个坐标的值均为不超过 $10^6$ 的非负整数