드론 집결

N대의 드론이 2차원 공간에 있다. i번째 드론은 (x_i, y_i) 위치에 있다. 드론은 상, 하, 좌, 우로 한 칸씩 이동할 수 있다.

k번째 출력값은 적어도 k대의 드론이 같은 위치에 모이도록 이동해야 하는 최소 이동 횟수이다. k = 1부터 k = N까지의 모든 값을 구하라.

참고로 2차원 평면 상에서 맨해튼 거리의 합을 최소화하는 집결 위치는 각각의 x좌표와 y좌표의 중앙값(median)이 된다.

입력

첫째 줄에 드론의 수 N이 주어진다. (1 ≤ N ≤ 50)
둘째 줄부터 N개의 줄에 걸쳐 각 드론의 좌표 x, y가 공백으로 구분되어 주어진다. (1 ≤ x, y ≤ 1,000,000)
드론들의 좌표가 모두 같을 수도 있다.

출력

첫째 줄에 N개의 정수를 공백으로 구분하여 출력한다. k번째 수는 k대의 드론을 한 곳에 모으는 최소 이동 횟수이다.

입출력 예시

입력 1

4
15 14
15 16
14 15
16 15

출력 1

0 2 3 4

입력 2

4
1 1
2 1
4 1
9 1

출력 2

0 1 3 10

입력 3

2
4 7
4 7

출력 3

0 0