题目描述

平面上分布了N个点，每个点的坐标都是一个整数。假设将一个点（x1,y1）移动到另一个点（x2,y2）的代价为两点之间的曼哈顿距离，也就是最小代价为|x1-x2|+|y1-y2|。

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

输入格式

• 第一行一个正整数N；
• 接下来N行，每行两个正整数xi和yi，为第i个点的坐标，坐标的值不超过1e6的非负整数。

输出格式

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

样例输入 1

3
1 2
5 6
3 4

样例输出 1

0
4
8

样例输入 2

4 
15 14
15 16
14 15
16 15

样例输出 2

0
2
3
4

样例输入 3

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

样例输出 3

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

说明

样例 1 解释

• 从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。

数据范围

对于100%的数据，满足1≤N≤50，每个坐标的值均为不超过1e6的非负整数。