Given $n$ circles $c_1,c_2,\dots ,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.

Input

The first line contains an integer $n$, denoting the number of circles $(1\le n\le 3\cdot {10}^5)$. 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}^9\le x_i,y_i\le {10}^9,1\le r_i\le {10}^9)$.

Output

Output $n$ integers $a_1,a_2,\dots ,a_n$ in the first line, where $a_i$ means that $c_i$ is eliminated by $c_{a_i}$.

Scoring

Subtask 1 (points: 7)

$n\le 5000$

Subtask 2 (points: 12)

$n\le 3\cdot {10}^5$, $y_i=0$ for all circles

Subtask 3 (points: 15)

$n\le 3\cdot {10}^5$, every circle intersects with at most 1 other circle

Subtask 4 (points: 23)

$n\le 3\cdot {10}^5$, all circles have the same radius

Subtask 5 (points: 30)

$n\le {10}^5$

Subtask 6 (points: 13)

$n\le 3\cdot {10}^5$

Sample Input

11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1

Sample Output

7 2 7 4 5 6 7 7 4 7 6

Note

The picture in the statements illustrates the first example.