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 N = 600010;
int qt[N];
long long ql[N], qr[N];
struct SegmentTree {
  long long sm[4 * N], op[4 * N], rev[4 * N];
  void change(int v, long long val, long long len) {
    if (val == 3) {
      sm[v] = len - sm[v];
      rev[v] ^= 1;
    } else {
      sm[v] = (val == 1) * len;
      op[v] = val;
      rev[v] = 0;
    }
  }
  void push(int v, int tl, int tm, int tr) {
    if (op[v] != 0) {
      change(v * 2, op[v], tm - tl + 1);
      change(v * 2 + 1, op[v], tr - tm);
      op[v] = 0;
    }
    if (rev[v] != 0) {
      change(v * 2, 3, tm - tl + 1);
      change(v * 2 + 1, 3, tr - tm);
      rev[v] = 0;
    }
  }
  int get(int v, int tl, int tr) {
    if (tl == tr) return tl;
    int tm = (tl + tr) >> 1;
    push(v, tl, tm, tr);
    if (sm[v * 2] == tm - tl + 1) return get(v * 2 + 1, tm + 1, tr);
    return get(v * 2, tl, tm);
  }
  void update(int v, int tl, int tr, int l, int r, long long val) {
    if (l > r) {
      return;
    }
    if (tl == l && tr == r) {
      change(v, val, tr - tl + 1);
      return;
    }
    int tm = (tl + tr) >> 1;
    push(v, tl, tm, tr);
    update(v * 2, tl, tm, l, min(r, tm), val);
    update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val);
    sm[v] = sm[v * 2] + sm[v * 2 + 1];
  }
} st;
void solve() {
  int n;
  cin >> n;
  vector<long long> cp = {1};
  for (int i = 0; i < n; i++) {
    cin >> qt[i] >> ql[i] >> qr[i];
    cp.push_back(ql[i]);
    cp.push_back(qr[i]);
    if (ql[i] - 1 >= 1) cp.push_back(ql[i] - 1);
    if (qr[i] - 1 >= 1) cp.push_back(qr[i] - 1);
    cp.push_back(ql[i] + 1);
    cp.push_back(qr[i] + 1);
  }
  sort((cp).begin(), (cp).end());
  cp.erase(unique((cp).begin(), (cp).end()), cp.end());
  int sz = cp.size();
  for (int i = 0; i < n; i++) {
    int l = lower_bound((cp).begin(), (cp).end(), ql[i]) - cp.begin();
    int r = lower_bound((cp).begin(), (cp).end(), qr[i]) - cp.begin();
    st.update(1, 0, sz - 1, l, r, qt[i]);
    cout << cp[st.get(1, 0, sz - 1)] << "\n";
  }
}
int main() {
  ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
  cout.setf(ios::fixed), cout.precision(20);
  solve();
}