You are given a set of points with integer coordinates. Each point has its own weight.
We can split the plane using a point of coordinates into four dials by drawing the vertical line in and the horizontal line in . We define the weight of a dial to be the sum of the weights of all the points in that dial. Furthermore, the of such a split is the maximum difference between the weight of two of its dials.
For each integer such that , find the minimum imbalance of a split that uses a point on the vertical line .
输入格式
The first line contains an integer ().
Each of the next lines contains three integers , , and (, ) --- the coordinates and weight of the -th point.
输出格式
The only line of the output should contain integers, the required minimum imbalances.
