CF164E.Polycarpus and Tasks

Polycarpus has many tasks. Each task is characterized by three integers l__i, r__i and t__i. Three integers (l__i, r__i, t__i) mean that to perform task i, one needs to choose an integer s__i (l__i ≤ s__i; s__i + t__i - 1 ≤ r__i), then the task will be carried out continuously for t__i units of time, starting at time s__i and up to time s__i + t__i - 1, inclusive. In other words, a task is performed for a continuous period of time lasting t__i, should be started no earlier than l__i, and completed no later than r__i.

Polycarpus's tasks have a surprising property: for any task j, k (with j < k) l__j < l__k and r__j < r__k.

Let's suppose there is an ordered set of tasks A, containing |A| tasks. We'll assume that a__j = (l__j, r__j, t__j) (1 ≤ j ≤ |A|). Also, we'll assume that the tasks are ordered by increasing l__j with the increase in number.

Let's consider the following recursive function f, whose argument is an ordered set of tasks A, and the result is an integer. The function f(A) is defined by the greedy algorithm, which is described below in a pseudo-language of programming.

• Step 1. , ans = 0.
• Step 2. We consider all tasks in the order of increasing of their numbers in the set A. Lets define the current task counter i = 0.
• Step 3. Consider the next task: i = i + 1. If i > |A| fulfilled, then go to the 8 step.
• Step 4. If you can get the task done starting at time s__i = max(ans + 1, l__i), then do the task i: s__i = max(ans + 1, l__i), ans = s__i + t__i - 1, . Go to the next task (step 3).
• Step 5. Otherwise, find such task , that first, task a__i can be done at time s__i = max, and secondly, the value of is positive and takes the maximum value among all b__k that satisfy the first condition. If you can choose multiple tasks as b__k, choose the one with the maximum number in set A.
• Step 6. If you managed to choose task b__k, then , . Go to the next task (step 3).
• Step 7. If you didn't manage to choose task b__k, then skip task i. Go to the next task (step 3).
• Step 8. Return ans as a result of executing f(A).

Polycarpus got entangled in all these formulas and definitions, so he asked you to simulate the execution of the function f, calculate the value of f(A).

波利卡普斯有许多任务。每个任务由三个整数 $l_i$、$r_i$ 和 $t_i$ 描述。三元组 $(l_i,\,r_i,\,t_i)$ 表示：为执行任务 $i$，需选择一个整数 $s_i$（满足 $l_i \le s_i$ 且 $s_i + t_i - 1 \le r_i$），该任务将从时刻 $s_i$ 开始、持续 $t_i$ 个时间单位，至时刻 $s_i + t_i - 1$ 结束（含端点）。换言之，任务需在一段连续的 $t_i$ 单位时间内完成，且必须不早于 $l_i$ 开始、不晚于 $r_i$ 结束。

波利卡普斯的任务具有一项特殊性质：对任意两个任务 $j$、$k$（满足 $j < k$），均有 $l_j < l_k$ 且 $r_j < r_k$。

设存在一个有序任务集合 $A$，其大小为 $|A|$。记 $a_j = (l_j,\,r_j,\,t_j)$（其中 $1 \le j \le |A|$），并假设这些任务按 $l_j$ 的升序编号排列。

现考虑如下递归函数 $f$，其输入为有序任务集合 $A$，输出为一个整数。函数 $f(A)$ 由以下贪心算法定义（以伪代码形式描述）：

• 步骤 1. ，$ans = 0$。
• 步骤 2. 按集合 $A$ 中任务编号递增顺序依次处理所有任务。令当前任务计数器 $i = 0$。
• 步骤 3. 处理下一个任务：$i = i + 1$。若 $i > |A|$，则跳转至步骤 8。
• 步骤 4. 若可将任务 $i$ 安排在时刻 $s_i = \max(ans + 1,\,l_i)$ 开始执行，则执行任务 $i$：令 $s_i = \max(ans + 1,\,l_i)$，$ans = s_i + t_i - 1$，。然后继续处理下一任务（返回步骤 3）。
• 步骤 5. 否则，寻找某个任务 ，使其满足：第一，任务 $a_i$ 可安排在时刻 $s_i = \max$ 开始执行；第二，值 为正，且在所有满足第一条件的 $b_k$ 中取最大值。若存在多个满足条件的 $b_k$，则选取在集合 $A$ 中编号最大的那个。
• 步骤 6. 若成功选定了任务 $b_k$，则 ，。然后继续处理下一任务（返回步骤 3）。
• 步骤 7. 若未能选定任务 $b_k$，则跳过任务 $i$。然后继续处理下一任务（返回步骤 3）。
• 步骤 8. 返回 $ans$ 作为 $f(A)$ 的执行结果。

波利卡普斯被这些公式和定义搞得晕头转向，因此他请你模拟函数 $f$ 的执行过程，并计算 $f(A)$ 的值。

The first line of the input contains a single integer n (1 ≤ n ≤ 105) — the number of tasks in set A.

Then n lines describe the tasks. The i-th line contains three space-separated integers l__i, r__i, t__i (1 ≤ l__i ≤ r__i ≤ 109, 1 ≤ t__i ≤ r__i - l__i + 1) — the description of the i-th task.

It is guaranteed that for any tasks j, k (considering that j < k) the following is true: l__j < l__k and r__j < r__k.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）——集合 $A$ 中任务的数量。

接下来 $n$ 行描述这些任务。第 $i$ 行包含三个用空格分隔的整数 $l_i$、$r_i$、$t_i$（$1 \leq l_i \leq r_i \leq 10^9$，$1 \leq t_i \leq r_i - l_i + 1$）——表示第 $i$ 个任务的描述。

保证对任意两个任务 $j$、$k$（假设 $j < k$），均有 $l_j < l_k$ 且 $r_j < r_k$。

For each task i print a single integer — the result of processing task i on the i-th iteration of the cycle (step 3) in function f(A). In the i-th line print:

• 0 — if you managed to add task i on step 4.
• -1 — if you didn't manage to add or replace task i (step 7).
• res__i (1 ≤ res__i ≤ n) — if you managed to replace the task (step 6): res__i equals the task number (in set A), that should be chosen as b__k and replaced by task a__i.

对每个任务 $i$，输出一个整数——即在函数 $f(A)$ 的第 $i$ 次循环迭代（步骤 3）中处理任务 $i$ 的结果。在第 $i$ 行输出：

• 0 —— 若你在步骤 4 成功添加了任务 $i$；
• -1 —— 若你既未成功添加也未成功替换任务 $i$（步骤 7）；
• $res_i$（其中 $1 \le res_i \le n$）—— 若你成功替换了任务（步骤 6）：$res_i$ 表示集合 $A$ 中应被选为 $b_k$ 并由任务 $a_i$ 替换的任务编号。