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 MAXN = 1e6 + 10;
long long n, in_l[MAXN], in_r[MAXN], in_o[MAXN];
long long val[MAXN << 1], tot;
struct Node {
  long long tag, sum;
  Node() { tag = -1; }
};
struct Segment_Tree {
  Node v[MAXN << 2];
  void PushUp(long long rt) { v[rt].sum = v[rt << 1].sum + v[rt << 1 | 1].sum; }
  void Change(long long l, long long r, long long C, long long rt) {
    v[rt].sum = (r - l + 1) * C;
    v[rt].tag = C;
  }
  void PushDown(long long l, long long r, long long rt) {
    long long mid = (l + r) >> 1;
    if (v[rt].tag != -1) {
      Change(l, mid, v[rt].tag, rt << 1);
      Change(mid + 1, r, v[rt].tag, rt << 1 | 1);
      v[rt].tag = -1;
    }
  }
  void Build_Tree(long long l, long long r, long long rt) {
    if (l == r) return v[rt].tag = 0, void();
    long long mid = (l + r) >> 1;
    Build_Tree(l, mid, rt << 1);
    Build_Tree(mid + 1, r, rt << 1 | 1);
    PushUp(rt);
  }
  void Update1(long long L, long long R, long long C, long long l, long long r,
               long long rt) {
    if (L <= l && r <= R) return Change(l, r, C, rt), void();
    long long mid = (l + r) >> 1;
    PushDown(l, r, rt);
    if (L <= mid) Update1(L, R, C, l, mid, rt << 1);
    if (R > mid) Update1(L, R, C, mid + 1, r, rt << 1 | 1);
    PushUp(rt);
  }
  void Rotate(long long L, long long R, long long l, long long r,
              long long rt) {
    if (L <= l && r <= R && v[rt].tag != -1)
      return v[rt].tag ^= 1, v[rt].sum = (r - l + 1) - v[rt].sum, void();
    long long mid = (l + r) >> 1;
    PushDown(l, r, rt);
    if (L <= mid) Rotate(L, R, l, mid, rt << 1);
    if (R > mid) Rotate(L, R, mid + 1, r, rt << 1 | 1);
    PushUp(rt);
  }
  long long Query(long long L, long long R, long long l, long long r,
                  long long rt) {
    if (l == r) return l;
    long long mid = (l + r) >> 1;
    PushDown(l, r, rt);
    if ((mid - l + 1) > v[rt << 1].sum)
      return Query(L, R, l, mid, rt << 1);
    else
      return Query(L, R, mid + 1, r, rt << 1 | 1);
  }
  void OutPut(long long l, long long r, long long rt) {
    if (l == r) return cout << l << ' ', void();
    long long mid = (l + r) >> 1;
    PushDown(l, r, rt);
    OutPut(l, mid, rt << 1);
    OutPut(mid + 1, r, rt << 1 | 1);
    PushUp(rt);
  }
} t;
long long id(long long x) {
  return lower_bound(val + 1, val + tot + 1, x) - val;
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  val[++tot] = 1;
  for (long long i = 1; i <= n; i++) {
    cin >> in_o[i] >> in_l[i] >> in_r[i];
    for (long long j = -1; j <= 1; j++) {
      if (in_l[i] + j >= 1) val[++tot] = in_l[i] + j;
      if (in_r[i] + j >= 1) val[++tot] = in_r[i] + j;
    }
  }
  sort(val + 1, val + tot + 1);
  tot = unique(val + 1, val + tot + 1) - val - 1;
  t.Build_Tree(1, tot, 1);
  for (long long i = 1; i <= n; i++) {
    long long opt = in_o[i], l = id(in_l[i]), r = id(in_r[i]);
    if (opt == 1)
      t.Update1(l, r, 1, 1, tot, 1);
    else if (opt == 2)
      t.Update1(l, r, 0, 1, tot, 1);
    else
      t.Rotate(l, r, 1, tot, 1);
    cout << val[t.Query(1, tot, 1, tot, 1)] << endl;
  }
  return 0;
}