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 x + 0.5 and the horizontal line in y + 0.5. We define the weight of a dial to be the sum of the weights of all the points in that dial. Furthermore, the imbalance of such a split is the maximum difference between the weight of two of its dials.
For each integer such that 1 \leq x < n, find the minimum imbalance of a split that uses a point on the vertical line .
The first line contains an integer (1 \leq n \leq 2 \cdot 10^5).
Each of the next lines contains three integers x_i, y_i, and w_i (1 \leq x_i, y_i \leq n, 1 \leq w_i \leq 10^9) — the coordinates and weight of the -th point.
The only line of the output should contain n - 1 integers, the required minimum imbalances.
Example 1
( points): 1 \leq n \leq 200;
( points): 1 \leq n \leq 5000;
( points): 1 \leq n \leq 100\,000;
( points): no further restrictions.