Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tags yet

No tag edit access

E. Polycarpus and Tasks

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarpus 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*).

Input

The first line of the input contains a single integer *n* (1 ≤ *n* ≤ 10^{5}) — 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^{9}, 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}.

Examples

Input

5

1 8 5

2 9 3

3 10 3

8 11 4

11 12 2

Output

0 0 1 0 -1

Input

13

1 8 5

2 9 4

3 10 1

4 11 3

8 12 5

9 13 5

10 14 5

11 15 1

12 16 1

13 17 1

14 18 3

15 19 3

16 20 2

Output

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

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/28/2017 08:32:45 (p1).

Desktop version, switch to mobile version.
User lists

Name |
---|