Minimum Total Cost to Aggregate K Points on a Plane

You are given N points on a plane with integer coordinates. When moving a point from \( (x_0,y_0) \) to \( (x_1,y_1) \), the cost incurred is \( |x_0-x_1|+|y_0-y_1| \). For every \( K \) where \( 1\le K\le N \), determine the minimum total cost required so that there exists a point where at least \( K \) of the given points are located (after moving, if necessary).

Note: You can choose any one point as the meeting point (which does not need to be one of the original points). However, it can be shown that there is always an optimal meeting point among the given points.

Hint: For a set of points, the optimal meeting point (minimizing Manhattan distance) is given by the median of the x-coordinates and the median of the y-coordinates respectively. In this problem, you can try each of the given points as a candidate meeting point, then for each candidate, calculate the cost for all points to move there, sort these costs, and pick the smallest total cost for choosing any \( K \) points.

inputFormat

The first line contains an integer \( N \) (\( 1 \leq N \leq \text{small} \)). Each of the next \( N \) lines contains two integers \( x \) and \( y \), representing the coordinates of a point on the plane.

outputFormat

Output \( N \) space-separated integers. The \( i^{th} \) number represents the minimum total cost required so that at least \( i \) points are located at the same coordinate after moving.

sample

3
0 0
0 10
10 0

0 10 20