Problem: You are given a set of integer numbers, initially it is empty. You should perform n queries.

There are three different types of queries: 

  * 1 l r — Add all missing numbers from the interval [l, r]
  * 2 l r — Remove all present numbers from the interval [l, r]
  * 3 l r — Invert the interval [l, r] — add all missing and remove all present numbers from the interval [l, r]



After each query you should output MEX of the set — the smallest positive (MEX ≥ 1) integer number which is not presented in the set.

Input

The first line contains one integer number n (1 ≤ n ≤ 105).

Next n lines contain three integer numbers t, l, r (1 ≤ t ≤ 3, 1 ≤ l ≤ r ≤ 1018) — type of the query, left and right bounds.

Output

Print MEX of the set after each query.

Examples

Input

3
1 3 4
3 1 6
2 1 3


Output

1
3
1


Input

4
1 1 3
3 5 6
2 4 4
3 1 6


Output

4
4
4
1

Note

Here are contents of the set after each query in the first example:

  1. {3, 4} — the interval [3, 4] is added 
  2. {1, 2, 5, 6} — numbers {3, 4} from the interval [1, 6] got deleted and all the others are added 
  3. {5, 6} — numbers {1, 2} got deleted 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int cnt0, n, op[N], st0, cnt;
long long a[N], b[N], val[N * 6];
struct stnode {
  int id, tp;
  long long val;
} stn[N * 6];
bool operator<(stnode x, stnode y) { return x.val < y.val; }
struct node {
  int l, r, s1, rev, lz, len;
  node *ls, *rs;
} pool[N * 2 * 6], *root;
node *build(int l, int r) {
  node *t = &pool[++cnt];
  t->l = l;
  t->r = r;
  t->lz = -1;
  t->len = r - l + 1;
  if (l == r) return t;
  int mid = l + r >> 1;
  t->ls = build(l, mid);
  t->rs = build(mid + 1, r);
  return t;
}
void upd(node *t) { t->s1 = t->ls->s1 + t->rs->s1; }
void pdn(node *t) {
  if (t->rev) {
    if (t->ls->lz == -1)
      t->ls->rev ^= 1;
    else
      t->ls->lz ^= 1;
    if (t->rs->lz == -1)
      t->rs->rev ^= 1;
    else
      t->rs->lz ^= 1;
    t->ls->s1 = t->ls->len - t->ls->s1;
    t->rs->s1 = t->rs->len - t->rs->s1;
    t->rev = 0;
  }
  if (t->lz != -1) {
    t->ls->lz = t->rs->lz = t->lz;
    t->ls->rev = t->rs->rev = 0;
    t->ls->s1 = t->lz * t->ls->len;
    t->rs->s1 = t->lz * t->rs->len;
    t->lz = -1;
  }
}
void chg(node *t, int l, int r, int tp) {
  if (l <= t->l && r >= t->r) {
    if (tp == -1) {
      if (t->lz != -1)
        t->lz ^= 1;
      else
        t->rev ^= 1;
      t->s1 = t->len - t->s1;
    } else {
      t->rev = 0;
      t->s1 = tp * t->len;
      t->lz = tp;
    }
    return;
  }
  pdn(t);
  int mid = t->l + t->r >> 1;
  if (l <= mid) chg(t->ls, l, r, tp);
  if (r > mid) chg(t->rs, l, r, tp);
  upd(t);
}
int qry(node *t) {
  if (t->len == 1) return t->l;
  pdn(t);
  if (t->ls->s1 ^ t->ls->len) return qry(t->ls);
  return qry(t->rs);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%lld%lld", op + i, a + i, b + i),
        stn[++st0].id = i, stn[st0].tp = 1, stn[st0].val = a[i],
        stn[++st0].id = i, stn[st0].tp = 2, stn[st0].val = b[i];
    if (a[i] != 1) stn[++st0].val = a[i] - 1;
    if (b[i] != 1) stn[++st0].val = b[i] - 1;
    stn[++st0].val = a[i] + 1;
    stn[++st0].val = b[i] + 1;
  }
  stn[++st0].val = 1;
  sort(stn + 1, stn + st0 + 1);
  for (int i = 1; i <= st0; i++) {
    cnt0 += 1 - (i != 1 && stn[i].val == stn[i - 1].val);
    if (stn[i].tp == 1) a[stn[i].id] = cnt0;
    if (stn[i].tp == 2) b[stn[i].id] = cnt0;
    val[cnt0] = stn[i].val;
  }
  val[++cnt0] = stn[st0].val + 1;
  root = build(1, cnt0);
  for (int i = 1; i <= n; i++) {
    if (op[i] == 1) chg(root, a[i], b[i], 1);
    if (op[i] == 2) chg(root, a[i], b[i], 0);
    if (op[i] == 3) chg(root, a[i], b[i], -1);
    printf("%lld\n", val[qry(root)]);
  }
}