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;
int t[401000], addt[401000], di[401000], addi[401000];
set<pair<int, int> > S;
set<pair<int, int> >::iterator it;
void push_up(int id) {
  int l = id * 2;
  int r = id * 2 + 1;
  t[id] = max(t[l], t[r]);
  di[id] = min(di[l], di[r]);
  return;
}
void push_down(int id) {
  int l = id * 2;
  int r = id * 2 + 1;
  if (addt[id]) {
    addt[r] += addt[id];
    addt[l] += addt[id];
    t[r] += addt[id];
    t[l] += addt[id];
    addt[id] = 0;
  }
  if (addi[id]) {
    addi[r] += addi[id];
    addi[l] += addi[id];
    di[l] += addi[id];
    di[r] += addi[id];
    addi[id] = 0;
  }
}
void build(int st, int en, int id) {
  t[id] = 0;
  di[id] = 1010001000;
  if (st == en) {
    return;
  }
  int mid = (st + en) >> 1;
  build(st, mid, id * 2);
  build(mid + 1, en, id * 2 + 1);
}
void cha(int l, int r, int st, int en, int id, int tt, int va) {
  if (l > en || r < st) return;
  if (l <= st && en <= r) {
    addt[id] += tt;
    t[id] += tt;
    di[id] += va;
    addi[id] += va;
    return;
  }
  push_down(id);
  int mid = (st + en) >> 1;
  cha(l, r, st, mid, id * 2, tt, va);
  cha(l, r, mid + 1, en, id * 2 + 1, tt, va);
  push_up(id);
}
int calcid(int st, int en, int id, int va) {
  if (st == en) {
    return st;
  }
  push_down(id);
  int mid = (st + en) >> 1;
  if (di[id * 2 + 1] < va) return calcid(mid + 1, en, id * 2 + 1, va);
  return calcid(st, mid, id * 2, va);
}
int Mx(int l, int r, int st, int en, int id) {
  if (l > en || st > r) return 0;
  if (l <= st && en <= r) return t[id];
  push_down(id);
  int mid = (st + en) >> 1;
  return max(Mx(l, r, st, mid, id * 2), Mx(l, r, mid + 1, en, id * 2 + 1));
}
int Mn(int l, int r, int st, int en, int id) {
  if (l > en || st > r) return 1010001000;
  if (l <= st && en <= r) return di[id];
  push_down(id);
  int mid = (st + en) >> 1;
  return min(Mn(l, r, st, mid, id * 2), Mn(l, r, mid + 1, en, id * 2 + 1));
}
int ti[401000];
int main() {
  int l, r;
  int n;
  scanf("%d", &n);
  int ans = 0;
  build(1, n, 1);
  int xx = 0;
  int Id = 0;
  ti[0] = 1;
  S.clear();
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", &l, &r, &ti[i]);
    r++;
    int stt = max(ans, l);
    if (stt + ti[i] <= r) {
      printf("0 ");
      pair<int, int> ab = pair<int, int>(ti[i], i);
      S.insert(ab);
      cha(i, i, 1, n, 1, ti[i], -1010001000 + stt - l);
      ans = stt + ti[i];
      xx = ti[i];
      Id = i;
      continue;
    }
    int st = xx;
    int en = 1010001000;
    while (en - st > 1) {
      int mid = (en + st) >> 1;
      int id = calcid(1, n, 1, mid);
      int xxx = Mx(id, n, 1, n, 1);
      if (xxx >= mid)
        st = mid;
      else
        en = mid;
    }
    if (i == 47) {
      for (it = S.begin(); it != S.end(); it++) {
      }
      int id = calcid(1, n, 1, 6);
      int xxx = Mx(id, n, 1, n, 1);
    }
    int id = calcid(1, n, 1, st);
    int st1 = max(l, ans - st);
    if (st1 + ti[i] > r || ans <= st1 + ti[i]) {
      printf("-1 ");
      continue;
    }
    int id1 = calcid(1, n, 1, st + 1);
    it = S.lower_bound(pair<int, int>(st + 1, 0));
    int id2 = 0;
    if (it != S.begin()) {
      it--;
      pair<int, int> ab = *it;
      if (ab.first == st) id2 = ab.second;
    }
    int stid;
    int s, e;
    if (id1 < id2)
      stid = id2;
    else {
      if (Mx(id, id1, 1, n, 1) < st)
        stid = id2;
      else {
        int s = id;
        int e = id1 + 1;
        while (e - s > 1) {
          int mid = (s + e) >> 1;
          if (Mx(mid, id1, 1, n, 1) < st)
            e = mid;
          else
            s = mid;
        }
        if (id2 > s)
          stid = id2;
        else
          stid = s;
      }
    }
    if (st == xx) {
      stid = Id;
    }
    if (!stid) {
      printf("%d %d %d %d %d %d\n", id, id1, id2, s, st, ti[96]);
      return 0;
    }
    printf("%d ", stid);
    pair<int, int> ab = pair<int, int>(ti[stid], stid);
    S.erase(ab);
    ab = pair<int, int>(ti[i], i);
    S.insert(ab);
    ans = st1 + ti[i];
    xx = ti[i];
    Id = i;
    cha(stid + 1, i - 1, 1, n, 1, 0, -st);
    cha(stid, stid, 1, n, 1, -ti[stid], 1010001000);
    cha(i, i, 1, n, 1, ti[i], -1010001000 + st1 - l);
  }
  puts("");
  return 0;
}