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>
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
long long read() {
  char ch = getchar();
  long long x = 0, f = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const int N = 4e5 + 10;
long long tree[N << 2];
long long lazy[N << 2];
long long lazy2[N << 2];
void pushup(int root) { tree[root] = tree[root << 1] + tree[root << 1 | 1]; }
void pushdown(int root, int l, int r) {
  int lenr = (r - l + 1) >> 1;
  int lenl = (r - l + 1) - lenr;
  if (lazy[root]) {
    lazy[root << 1] = lazy[root << 1 | 1] = lazy[root];
    lazy2[root << 1] = lazy2[root << 1 | 1] = 0;
    if (lazy[root] == 1) {
      tree[root << 1] = lenl, tree[root << 1 | 1] = lenr;
    } else if (lazy[root] == 2) {
      tree[root << 1] = tree[root << 1 | 1] = 0;
    }
    lazy[root] = 0;
  }
  if (lazy2[root] % 2) {
    lazy2[root << 1] += lazy2[root];
    lazy2[root << 1 | 1] += lazy2[root];
    tree[root << 1] = lenl - tree[root << 1];
    tree[root << 1 | 1] = lenr - tree[root << 1 | 1];
    lazy2[root] = 0;
  }
}
void build(int l, int r, int root) {
  lazy[root] = 0;
  lazy2[root] = 0;
  if (l == r) {
    tree[root] = 0;
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, root << 1);
  build(mid + 1, r, root << 1 | 1);
  pushup(root);
}
void update(int l, int r, int root, int lf, int rt, int op) {
  if (lf <= l && r <= rt) {
    if (op == 1) {
      tree[root] = r - l + 1;
      lazy[root] = 1;
      lazy2[root] = 0;
    } else if (op == 2) {
      tree[root] = 0;
      lazy[root] = 2;
      lazy2[root] = 0;
    } else {
      tree[root] = r - l + 1 - tree[root];
      lazy2[root]++;
    }
    return;
  }
  pushdown(root, l, r);
  int mid = (l + r) >> 1;
  if (lf <= mid) {
    update(l, mid, root << 1, lf, rt, op);
  }
  if (rt > mid) update(mid + 1, r, root << 1 | 1, lf, rt, op);
  pushup(root);
}
int querry(int l, int r, int root, int lf, int rt) {
  if (lf <= l && r <= rt) {
    return tree[root];
  }
  pushdown(root, l, r);
  int mid = (l + r) >> 1;
  int ans = 0;
  if (lf <= mid) ans += querry(l, mid, root << 1, lf, rt);
  if (rt > mid) ans += querry(mid + 1, r, root << 1 | 1, lf, rt);
  return ans;
}
vector<long long> hi;
struct node {
  long long l, r, op;
} a[N];
long long t, l, r, n;
int findpos(long long val) {
  return lower_bound(hi.begin(), hi.end(), val) - hi.begin();
}
int main() {
  n = read();
  int lim = n;
  for (int i = 0; i < n; i++) {
    t = read(), l = read(), r = read();
    a[i] = node{l, r, t};
    hi.push_back(l), hi.push_back(r);
    hi.push_back(r + 1);
    hi.push_back(l + 1);
  }
  hi.push_back(1);
  sort(hi.begin(), hi.end());
  hi.erase(unique(hi.begin(), hi.end()), hi.end());
  n = hi.size();
  build(1, n, 1);
  for (int i = 0; i < lim; i++) {
    t = a[i].op;
    l = findpos(a[i].l) + 1;
    r = findpos(a[i].r) + 1;
    update(1, n, 1, l, r, t);
    int l = 0;
    int r = n + 1;
    while (r - 1 > l) {
      int midd = (r + l) >> 1;
      int temp = querry(1, n, 1, 1, midd);
      if (temp == midd)
        l = midd;
      else
        r = midd;
    }
    printf("%lld\n", hi[r - 1]);
  }
  return 0;
}