Polycarpus and Tasks

3000ms

262144K

Description:

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. $\text{[math]}$ , 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, $\text{[math]}$ . Go to the next task (step 3).
Step 5. Otherwise, find such task $\text{[math]}$ , that first, task a_i can be done at time s_i = max $\text{[math]}$ , and secondly, the value of $\text{[math]}$ 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 $\text{[math]}$ , $\text{[math]}$ . 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).

Input:

The first line of the input contains a single integer n (1 ≤ n ≤ 10⁵) — 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 ≤ 10⁹, 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.

Output:

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.

Sample Input:

Sample Output:

0 0 1 0 -1

Sample Input:

Sample Output:

0 0 0 2 -1 -1 0 0 0 0 7 0 12

Informação

Provedor Codeforces

Código CF164E