题目描述

平面上有 $N$ 个点，第 $i$ 个点的坐标为 $(x_i,y_i)$。将点 $(x_1,y_1)$ 移动到点 $(x_2,y_2)$ 的代价为 $|x_1-x_2|+|y_1-y_2|$。

对于每个 $K=1,2,\ldots,N$，从给定的 $N$ 个点中选择恰好 $K$ 个点，并把它们移动到同一个坐标。目标坐标可以是平面上的任意整数坐标，不要求原来存在给定的点。

请分别求出每个 $K$ 对应的最小总代价。

输入格式

第一行包含一个正整数 $N$，表示点的数量。

接下来 $N$ 行，每行包含两个非负整数 $x_i,y_i$，表示一个点的坐标。

输出格式

输出 $N$ 行，第 $K$ 行输出一个整数，表示选择 $K$ 个点并将它们移动到同一坐标的最小总代价。

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

数据范围与提示

• $1 \le N \le 50$
• $0 \le x_i,y_i \le 10^6$