Checkers

Time limit2sMemory limit128 MB

Summary

For each k, find the fewest single-cell moves to bring at least k checkers onto one cell. Manhattan distances decide the cost.

Level: Medium6 of 10
Topics: Math, Sorting, Greedy
Solved: No attempts yet

Problem

There are N checkers on a very large board. Checker i is located at (xi, yi). More than one checker may occupy the same cell. One move consists of moving one checker by one cell in exactly one of four directions: up, left, right, or down.

For each k from 1 to N, determine the minimum number of moves needed so that at least k checkers are gathered on the same cell.

Input

The first line contains N. N is a positive integer no greater than 50.

Each of the next N lines contains the x-coordinate and y-coordinate of one checker. Every coordinate is a positive integer no greater than 1,000,000.

Output

Print N integers on one line. The k-th integer must be the minimum number of moves required to make at least k checkers occupy the same cell.

Examples3

Example 1
Input
```
4
15 14
15 16
14 15
16 15
```
Expected output
```
0 2 3 4
```
Example 2
Input
```
4
1 1
2 1
4 1
9 1
```
Expected output
```
0 1 3 10
```
Example 3
Input
```
2
4 7
4 7
```
Expected output
```
0 0
```