15767번 - Circle selection 다국어

문제

Given n circles c₁, c₂, . . . , c_n on a flat Cartesian plane. We attempt to do the following:

1. Find the circle c_i with the largest radius. If there are multiple candidates all having the same (largest) radius, choose the one with the smallest index. (i.e. minimize i).
2. Remove c_i and all the circles intersecting with c_i. Two circles intersect if there exists a point included by both circles. A point is included by a circle if it is located in the circle or on the border of the circle.
3. Repeat 1 and 2 until there is no circle left.

We say c_i is eliminated by c_j if c_j is the chosen circle in the iteration where c_i is removed. For each circle, find out the circle by which it is eliminated.

입력

The first line contains an integer n, denoting the number of circles (1 ≤ n ≤ 3 · 10⁵). Each of the next n lines contains three integers x_i, y_i, r_i, representing the x-coordinate, the y-coordinate, and the radius of the circle c_i (−10⁹ ≤ x_i, y_i ≤ 10⁹, 1 ≤ r_i ≤ 10⁹).

출력

Output n integers a₁, a₂, . . . , a_n in the first line, where a_i means that c_i is eliminated by c_ai.

제한

힌트

The picture in the statements illustrates the first example.