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;
long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
long long n, t[300005], l[300005], r[300005], a[300005], cnt;
struct Segment_Tree {
  long long v[300005 << 2], rev[300005 << 2], tag[300005 << 2], L[300005 << 2],
      R[300005 << 2];
  void build(long long l, long long r, long long k) {
    v[k] = 0;
    rev[k] = 0;
    tag[k] = -1;
    L[k] = l;
    R[k] = r;
    if (l == r) return;
    long long mid = (l + r) >> 1;
    build(l, mid, k << 1);
    build(mid + 1, r, k << 1 | 1);
  }
  void pushup(long long k) { v[k] = v[k << 1] + v[k << 1 | 1]; }
  void pushdown(long long k) {
    if (tag[k] != -1) {
      tag[k << 1] = tag[k << 1 | 1] = tag[k];
      rev[k << 1] = rev[k << 1 | 1] = 0;
      if (tag[k]) {
        v[k << 1] = R[k << 1] - L[k << 1] + 1;
        v[k << 1 | 1] = R[k << 1 | 1] - L[k << 1 | 1] + 1;
      } else
        v[k << 1] = v[k << 1 | 1] = 0;
      tag[k] = -1;
    }
    if (rev[k]) {
      if (tag[k << 1] != -1)
        tag[k << 1] ^= 1;
      else
        rev[k << 1] ^= 1;
      if (tag[k << 1 | 1] != -1)
        tag[k << 1 | 1] ^= 1;
      else
        rev[k << 1 | 1] ^= 1;
      v[k << 1] = R[k << 1] - L[k << 1] + 1 - v[k << 1];
      v[k << 1 | 1] = R[k << 1 | 1] - L[k << 1 | 1] + 1 - v[k << 1 | 1];
      rev[k] = 0;
    }
  }
  void modify(long long l, long long r, long long k, long long x, long long y,
              long long opt) {
    if (l >= x && r <= y) {
      if (opt == 1) {
        tag[k] = 1;
        v[k] = r - l + 1;
        rev[k] = 0;
      } else if (opt == 2) {
        tag[k] = 0;
        v[k] = 0;
        rev[k] = 0;
      } else {
        if (tag[k] == -1)
          rev[k] ^= 1;
        else
          tag[k] ^= 1;
        v[k] = r - l + 1 - v[k];
      }
      return;
    }
    pushdown(k);
    long long mid = (l + r) >> 1;
    if (x <= mid) modify(l, mid, k << 1, x, y, opt);
    if (y > mid) modify(mid + 1, r, k << 1 | 1, x, y, opt);
    pushup(k);
  }
  long long query(long long l, long long r, long long k) {
    if (l == r) return l;
    pushdown(k);
    long long mid = (l + r) >> 1;
    if (v[k << 1] < R[k << 1] - L[k << 1] + 1) return query(l, mid, k << 1);
    return query(mid + 1, r, k << 1 | 1);
  }
} T;
signed main() {
  n = read();
  a[++cnt] = 1;
  for (long long i = 1; i <= n; i++) {
    t[i] = read();
    l[i] = read();
    r[i] = read();
    a[++cnt] = l[i];
    a[++cnt] = r[i];
    a[++cnt] = r[i] + 1;
  }
  sort(a + 1, a + 1 + cnt);
  long long tot = unique(a + 1, a + 1 + cnt) - a - 1;
  T.build(1, tot, 1);
  for (long long i = 1; i <= n; i++) {
    l[i] = lower_bound(a + 1, a + 1 + tot, l[i]) - a;
    r[i] = lower_bound(a + 1, a + 1 + tot, r[i]) - a;
    T.modify(1, tot, 1, l[i], r[i], t[i]);
    printf("%lld\n", a[T.query(1, tot, 1)]);
  }
}