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;
vector<int> adj[200005];
int xMove[] = {0, 1, 0, -1, 1, 1, -1, -1, 2, 2, -2, -2, 1, 1, -1, -1};
int yMove[] = {1, 0, -1, 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 2, -2};
int seg[200005 * 4], lazy[200005 * 4];
void propagate(int pos, int tlo, int thi) {
  if (lazy[pos] == 1) {
    seg[pos] = (thi - tlo + 1);
    if (tlo != thi) {
      lazy[2 * pos + 1] = 1;
      lazy[2 * pos + 2] = 1;
    }
  } else if (lazy[pos] == 2) {
    seg[pos] = 0;
    if (tlo != thi) {
      lazy[2 * pos + 1] = 2;
      lazy[2 * pos + 2] = 2;
    }
  } else if (lazy[pos] == 3) {
    seg[pos] = thi - tlo + 1 - seg[pos];
    if (tlo != thi) {
      if (lazy[2 * pos + 1] == 1)
        lazy[2 * pos + 1] = 2;
      else if (lazy[2 * pos + 1] == 2)
        lazy[2 * pos + 1] = 1;
      else if (lazy[2 * pos + 1] == 3)
        lazy[2 * pos + 1] = 0;
      else
        lazy[2 * pos + 1] = 3;
      if (lazy[2 * pos + 2] == 1)
        lazy[2 * pos + 2] = 2;
      else if (lazy[2 * pos + 2] == 2)
        lazy[2 * pos + 2] = 1;
      else if (lazy[2 * pos + 2] == 3)
        lazy[2 * pos + 2] = 0;
      else
        lazy[2 * pos + 2] = 3;
    }
  }
  lazy[pos] = 0;
}
void update_range(int pos, int tlo, int thi, int ulo, int uhi, int uv) {
  propagate(pos, tlo, thi);
  if (tlo > uhi or thi < ulo) return;
  if (ulo <= tlo and thi <= uhi) {
    lazy[pos] = uv;
    propagate(pos, tlo, thi);
    return;
  }
  int mid = (tlo + thi) >> 1;
  update_range(2 * pos + 1, tlo, mid, ulo, uhi, uv);
  update_range(2 * pos + 2, mid + 1, thi, ulo, uhi, uv);
  seg[pos] = seg[2 * pos + 1] + seg[2 * pos + 2];
}
int query(int pos, int tlo, int thi) {
  propagate(pos, tlo, thi);
  if (tlo == thi) return tlo;
  int mid = (tlo + thi) >> 1;
  propagate(2 * pos + 1, tlo, mid);
  if (seg[2 * pos + 1] < mid - tlo + 1)
    return query(2 * pos + 1, tlo, mid);
  else
    return query(2 * pos + 2, mid + 1, thi);
}
int main() {
  cin.tie(0), cout.tie(0);
  ios_base::sync_with_stdio(0);
  cout.setf(ios::fixed);
  cout.precision(10);
  int TC = 1;
  int n, m, k, q;
  for (int t1 = 1; t1 <= TC; t1++) {
    cin >> n;
    vector<array<long long int, 3> > vec(n);
    map<long long int, int> mp;
    map<int, long long int> rev_mp;
    mp[1] = 0;
    for (auto &[t, l, r] : vec) {
      cin >> t >> l >> r;
      mp[l] = 0;
      mp[r] = 0;
      mp[r + 1] = 0;
    }
    int cur = 0;
    for (auto &[k, v] : mp) v = ++cur, rev_mp[cur] = k;
    for (auto &[t, l, r] : vec) {
      update_range(0, 1, cur, mp[l], mp[r], t);
      int mex = query(0, 1, cur);
      cout << rev_mp[mex] << "\n";
    }
  }
  return 0;
}