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

Polycarpus's tasks have a surprising property: for any task j, k (with j < k) lj < lk and rj < rk.

Let's suppose there is an ordered set of tasks A, containing |A| tasks. We'll assume that aj = (lj, rj, tj) (1 ≤ j ≤ |A|). Also, we'll assume that the tasks are ordered by increasing lj 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. <image>, 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 si = max(ans + 1, li), then do the task i: si = max(ans + 1, li), ans = si + ti - 1, <image>. Go to the next task (step 3). 
  * Step 5. Otherwise, find such task <image>, that first, task ai can be done at time si = max<image>, and secondly, the value of <image> is positive and takes the maximum value among all bk that satisfy the first condition. If you can choose multiple tasks as bk, choose the one with the maximum number in set A. 
  * Step 6. If you managed to choose task bk, then <image>, <image>. Go to the next task (step 3). 
  * Step 7. If you didn't manage to choose task bk, 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 ≤ 105) — the number of tasks in set A. 

Then n lines describe the tasks. The i-th line contains three space-separated integers li, ri, ti (1 ≤ li ≤ ri ≤ 109, 1 ≤ ti ≤ ri - li + 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: lj < lk and rj < rk.

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). 
  * resi (1 ≤ resi ≤ n) — if you managed to replace the task (step 6): resi equals the task number (in set A), that should be chosen as bk and replaced by task ai. 

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 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
struct elem {
  int l, p, t, ind;
  elem() {}
  elem(int inl, int inp, int intt, int inind) {
    l = inl;
    p = inp;
    t = intt;
    ind = inind;
  }
};
int base = 315;
int n;
elem v[1000000];
int btmax[1000000];
int bttope[1000000];
int cuantos[1000000];
int bdesp[1000000];
void recalcula(int b) {
  int ini = b * base;
  int fin = ini + cuantos[b] - 1;
  int& tmax = btmax[b];
  int& ttope = bttope[b];
  int& desp = bdesp[b];
  for (int i = ini; i <= fin; i++) v[i].p -= desp;
  tmax = 0;
  ttope = 2000000000;
  desp = 0;
  for (int i = fin; i >= ini; i--) {
    tmax = max(tmax, min(v[i].t, ttope));
    ttope = min(ttope, v[i].p - v[i].l);
  }
}
int ianterior(int b) {
  for (; b >= 0; b--)
    if (cuantos[b]) return base * b + cuantos[b] - 1;
  return -1;
}
void elimina(int b, int ttope, int iultimo) {
  recalcula(b);
  int ini = b * base;
  int fin = ini + cuantos[b] - 1;
  int tmax = 0, imax;
  for (int i = fin; i >= ini and tmax < ttope; i--) {
    if (v[i].t > tmax) {
      tmax = min(v[i].t, ttope);
      imax = i;
    }
    ttope = min(ttope, v[i].p - v[i].l);
  }
  if (imax == iultimo)
    cout << -1 << endl;
  else
    cout << v[imax].ind << endl;
  for (int i = imax; i < fin; i++) {
    v[i] = v[i + 1];
    v[i].p -= tmax;
  }
  cuantos[b]--;
  recalcula(b);
  int bultimo = iultimo / base;
  b++;
  for (; b <= bultimo; b++) {
    bdesp[b] += tmax;
    if (btmax[b] >= bttope[b] - bdesp[b]) recalcula(b);
  }
  recalcula(bultimo);
}
void elimina(int iultimo) {
  int b = iultimo / base;
  int tmax = 0, ttope = 2000000000, bmax;
  for (; b >= 0; b--) {
    if (max(tmax, btmax[b]) >= min(ttope, bttope[b] - bdesp[b])) {
      if (btmax[b] > tmax) {
        elimina(b, ttope, iultimo);
        return;
      }
      elimina(bmax, 2000000000, iultimo);
      return;
    }
    if (btmax[b] > tmax) {
      tmax = btmax[b];
      bmax = b;
    }
    ttope = min(ttope, bttope[b] - bdesp[b]);
  }
  elimina(bmax, 2000000000, iultimo);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int l, r, t;
    cin >> l >> r >> t;
    if (i == 1) {
      cout << 0 << endl;
      v[0] = elem(l, l, t, i);
      cuantos[0]++;
      recalcula(0);
    } else {
      int b = (i - 1) / base;
      int iultimo, iant;
      if (cuantos[b]) {
        iant = b * base + cuantos[b] - 1;
        iultimo = iant + 1;
      } else {
        iant = ianterior(b - 1);
        iultimo = b * base;
      }
      v[iultimo] =
          elem(l, max(l, v[iant].p - bdesp[iant / base] + v[iant].t), t, i);
      cuantos[b]++;
      recalcula(b);
      if (v[iultimo].p + t - 1 <= r) {
        cout << 0 << endl;
      } else {
        elimina(iultimo);
      }
    }
  }
}