Checkers

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.

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.

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.