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;
template <typename T>
void out(T x) {
  cout << x << endl;
  exit(0);
}
using ll = long long;
const ll mod = 1e9 + 7;
const int maxn = 1e6 + 5;
int q;
vector<ll> ord;
ll type[maxn], L[maxn], R[maxn];
int tree[maxn * 4];
int lazy_set[maxn * 4];
int lazy_inv[maxn * 4];
void push(int v, int tl, int tr) {
  if (lazy_set[v] == -1 && lazy_inv[v] == 0) {
    return;
  }
  int tm = (tl + tr) / 2;
  if (lazy_set[v] != -1) {
    lazy_set[2 * v] = lazy_set[v];
    tree[2 * v] = (tm - tl + 1) * lazy_set[v];
    lazy_inv[2 * v] = 0;
    lazy_set[2 * v + 1] = lazy_set[v];
    tree[2 * v + 1] = (tr - tm) * lazy_set[v];
    lazy_inv[2 * v + 1] = 0;
  } else {
    if (lazy_set[2 * v] != -1) {
      lazy_set[2 * v] ^= 1;
      lazy_inv[2 * v] = 0;
    } else {
      lazy_inv[2 * v] ^= 1;
    }
    tree[2 * v] = (tm - tl + 1) - tree[2 * v];
    if (lazy_set[2 * v + 1] != -1) {
      lazy_set[2 * v + 1] ^= 1;
      lazy_inv[2 * v + 1] = 0;
    } else {
      lazy_inv[2 * v + 1] ^= 1;
    }
    tree[2 * v + 1] = (tr - tm) - tree[2 * v + 1];
  }
  lazy_set[v] = -1;
  lazy_inv[v] = 0;
}
void upd(int v, int tl, int tr, int l, int r, int val) {
  if (l > tr || r < tl) return;
  if (l <= tl && tr <= r) {
    tree[v] = (tr - tl + 1) * val;
    lazy_set[v] = val;
    lazy_inv[v] = 0;
  } else {
    int tm = (tl + tr) / 2;
    push(v, tl, tr);
    upd(2 * v, tl, tm, l, r, val);
    upd(2 * v + 1, tm + 1, tr, l, r, val);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
  }
}
void inv(int v, int tl, int tr, int l, int r) {
  if (l > tr || r < tl) return;
  if (l <= tl && tr <= r) {
    if (lazy_set[v] == -1) {
      lazy_inv[v] ^= 1;
      tree[v] = (tr - tl + 1) - tree[v];
    } else {
      lazy_set[v] ^= 1;
      lazy_inv[v] = 0;
      tree[v] = (tr - tl + 1) - tree[v];
    }
  } else {
    int tm = (tl + tr) / 2;
    push(v, tl, tr);
    inv(2 * v, tl, tm, l, r);
    inv(2 * v + 1, tm + 1, tr, l, r);
    tree[v] = tree[2 * v] + tree[2 * v + 1];
  }
}
int qry(int v, int tl, int tr, int l, int r) {
  if (l > tr || r < tl) return 0;
  if (l <= tl && tr <= r) {
    return tree[v];
  } else {
    int tm = (tl + tr) / 2;
    push(v, tl, tr);
    return qry(2 * v, tl, tm, l, r) + qry(2 * v + 1, tm + 1, tr, l, r);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> type[i] >> L[i] >> R[i];
    ord.push_back(L[i]);
    ord.push_back(R[i]);
    ord.push_back(R[i] + 1);
  }
  ord.push_back(-1);
  ord.push_back(1);
  sort(ord.begin(), ord.end());
  ord.erase(unique(ord.begin(), ord.end()), ord.end());
  int n = ord.size();
  n--;
  memset(lazy_set, -1, sizeof(lazy_set));
  for (int i = 0; i < q; i++) {
    int li = lower_bound(ord.begin(), ord.end(), L[i]) - ord.begin();
    int ri = lower_bound(ord.begin(), ord.end(), R[i]) - ord.begin();
    if (type[i] == 1) {
      upd(1, 1, n, li, ri, 1);
    }
    if (type[i] == 2) {
      upd(1, 1, n, li, ri, 0);
    }
    if (type[i] == 3) {
      inv(1, 1, n, li, ri);
    }
    int lo = 0;
    int hi = n + 1;
    while (hi - lo > 1) {
      int mid = (hi + lo) / 2;
      if (qry(1, 1, n, 1, mid) >= mid) {
        lo = mid;
      } else {
        hi = mid;
      }
    }
    int idx = lo;
    assert(idx < n);
    idx++;
    cout << ord[idx] << "\n";
  }
  return 0;
}