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*)$.

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*}$.