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;
int n, m;
long long q[500005];
struct Operation {
  int t;
  long long l, r;
} op[500005];
struct Segment_Tree {
  int l, r, len;
  int sum, tag, rev;
} t[500005 << 2];
inline int Find(long long v) { return lower_bound(q + 1, q + m + 1, v) - q; }
inline void Pushup(int k) {
  t[k].sum = t[k << 1].sum + t[k << 1 | 1].sum;
  return;
}
inline void Pushdown(int k) {
  if (~t[k].tag) {
    t[k << 1].tag = t[k].tag;
    t[k << 1].sum = t[k].tag * t[k << 1].len;
    t[k << 1 | 1].tag = t[k].tag;
    t[k << 1 | 1].sum = t[k].tag * t[k << 1 | 1].len;
    t[k << 1].rev = t[k << 1 | 1].rev = 0;
    t[k].tag = -1;
  }
  if (t[k].rev) {
    if (~t[k << 1].tag)
      t[k << 1].tag ^= 1;
    else
      t[k << 1].rev ^= 1;
    if (~t[k << 1 | 1].tag)
      t[k << 1 | 1].tag ^= 1;
    else
      t[k << 1 | 1].rev ^= 1;
    t[k << 1].sum = t[k << 1].len - t[k << 1].sum;
    t[k << 1 | 1].sum = t[k << 1 | 1].len - t[k << 1 | 1].sum;
    t[k].rev ^= 1;
  }
  return;
}
inline void Build(int k, int l, int r) {
  t[k].l = l;
  t[k].r = r;
  t[k].len = (r - l + 1);
  t[k].sum = t[k].rev = 0;
  t[k].tag = -1;
  if (l == r) return;
  int mid = (l + r) >> 1;
  Build(k << 1, l, mid);
  Build(k << 1 | 1, mid + 1, r);
  return;
}
inline void Modify(int k, int l, int r, int v) {
  if (l <= t[k].l && t[k].r <= r) {
    if (~v) {
      t[k].tag = v;
      t[k].rev = 0;
      t[k].sum = v * t[k].len;
    } else {
      if (~t[k].tag)
        t[k].tag ^= 1;
      else
        t[k].rev ^= 1;
      t[k].sum = t[k].len - t[k].sum;
    }
    return;
  }
  Pushdown(k);
  int mid = (t[k].l + t[k].r) >> 1;
  if (l <= mid) Modify(k << 1, l, r, v);
  if (mid < r) Modify(k << 1 | 1, l, r, v);
  Pushup(k);
  return;
}
inline int Query(int k) {
  if (t[k].len == 1) return t[k].l;
  Pushdown(k);
  if (t[k << 1].sum < t[k << 1].len)
    return Query(k << 1);
  else
    return Query(k << 1 | 1);
}
int main() {
  scanf("%d", &n);
  q[++m] = 1;
  for (register int i = 1; i <= n; i++) {
    scanf("%d%lld%lld", &op[i].t, &op[i].l, &op[i].r);
    q[++m] = op[i].l;
    q[++m] = op[i].r;
    q[++m] = op[i].r + 1;
  }
  sort(q + 1, q + m + 1);
  m = unique(q + 1, q + m + 1) - q - 1;
  Build(1, 1, m);
  for (register int i = 1; i <= n; i++) {
    int tl = Find(op[i].l), tr = Find(op[i].r);
    if (op[i].t == 1) Modify(1, tl, tr, 1);
    if (op[i].t == 2) Modify(1, tl, tr, 0);
    if (op[i].t == 3) Modify(1, tl, tr, -1);
    printf("%lld\n", q[Query(1)]);
  }
  return 0;
}