给定平面直角坐标系上的 $n$ 个圆 $c_1, c_2, \dots, c_n$。我们尝试进行以下操作：

1. 找到半径最大的圆 $c_i$。如果有多个候选圆具有相同的（最大）半径，则选择索引最小的一个（即最小化 $i$）。
2. 移除 $c_i$ 以及所有与 $c_i$ 相交的圆。如果两个圆存在公共点，则称它们相交。一个点被圆包含，当且仅当它位于圆内或圆的边界上。
3. 重复步骤 1 和 2，直到没有圆剩余。

如果 $c_i$ 在某次迭代中被选中的圆 $c_j$ 移除，则称 $c_i$ 被 $c_j$ 消除。对于每个圆，找出消除它的圆。

输入格式

第一行包含一个整数 $n$，表示圆的数量 ($1 \le n \le 3 \cdot 10^5$)。接下来的 $n$ 行，每行包含三个整数 $x_i, y_i, r_i$，分别表示圆 $c_i$ 的圆心坐标和半径 ($-10^9 \le x_i, y_i \le 10^9, 1 \le r_i \le 10^9$)。

输出格式

在第一行输出 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 表示 $c_i$ 被 $c_{a_i}$ 消除。

子任务

• 子任务 1（7 分）：$n \le 5000$
• 子任务 2（12 分）：$n \le 3 \cdot 10^5$，$y_i = 0$（对于所有圆）
• 子任务 3（15 分）：$n \le 3 \cdot 10^5$，每个圆最多与 1 个其他圆相交
• 子任务 4（23 分）：$n \le 3 \cdot 10^5$，所有圆的半径相同
• 子任务 5（30 分）：$n \le 10^5$
• 子任务 6（13 分）：$n \le 3 \cdot 10^5$

样例

输入 1

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

输出 1

7 2 7 4 5 6 7 7 4 7 6

说明

题目中的图片展示了第一个样例。