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;
int dx[] = {+1, -1, 0, 0};
int dy[] = {0, 0, +1, -1};
int n, t[1000005];
long long l[1000005], r[1000005];
set<long long> st;
map<long long, int> MP;
long long lol[1000005];
int tree[1000005 * 4];
int lazy[1000005 * 4];
void process(int *cnd, int lz) {
  if (lz == 1)
    (*cnd) = 1;
  else if (lz == -1)
    (*cnd) = -1;
  else if (lz == 2) {
    if ((*cnd) == 1)
      (*cnd) = -1;
    else if ((*cnd) == -1)
      (*cnd) = 1;
    else if ((*cnd) == 0)
      (*cnd) = 2;
    else if ((*cnd) == 2)
      (*cnd) = 0;
  }
}
void propagate(int nd, int st, int en) {
  if (st != en) {
    process(&lazy[nd * 2], lazy[nd]);
    process(&lazy[nd * 2 + 1], lazy[nd]);
    process(&tree[nd], lazy[nd]);
  } else
    process(&tree[nd], lazy[nd]);
  lazy[nd] = 0;
}
void build(int nd, int st, int en) {
  if (st == en) {
    tree[nd] = -1;
    return;
  }
  int mid = (st + en) / 2;
  build(2 * nd, st, mid);
  build(2 * nd + 1, mid + 1, en);
  tree[nd] = -1;
}
void update(int nd, int st, int en, int l, int r, int val) {
  if (lazy[nd]) propagate(nd, st, en);
  if (r < st || en < l)
    return;
  else if (l <= st && en <= r) {
    lazy[nd] = val;
    propagate(nd, st, en);
  } else {
    int mid = (st + en) / 2;
    update(2 * nd, st, mid, l, r, val);
    update(2 * nd + 1, mid + 1, en, l, r, val);
    propagate(2 * nd, st, mid);
    propagate(2 * nd + 1, mid + 1, en);
    if (tree[2 * nd] == tree[2 * nd + 1] && tree[2 * nd] == 1)
      tree[nd] = 1;
    else if (tree[2 * nd] == tree[2 * nd + 1] && tree[2 * nd] == -1)
      tree[nd] = -1;
    else
      tree[nd] = 0;
  }
}
long long query(int nd, int st, int en) {
  if (lazy[nd]) propagate(nd, st, en);
  if (tree[nd] == 1) return -1;
  if (st == en) return lol[st];
  long long res = -1;
  int mid = (st + en) / 2;
  res = query(nd * 2, st, mid);
  if (res == -1) res = query(nd * 2 + 1, mid + 1, en);
  propagate(nd * 2, st, mid);
  propagate(nd * 2 + 1, mid + 1, en);
  if (tree[2 * nd] == tree[2 * nd + 1] && tree[2 * nd] == 1)
    tree[nd] = 1;
  else if (tree[2 * nd] == tree[2 * nd + 1] && tree[2 * nd] == -1)
    tree[nd] = -1;
  else
    tree[nd] = 0;
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n;
  st.insert(1);
  for (int i = 1; i <= n; i++) {
    cin >> t[i] >> l[i] >> r[i];
    st.insert(l[i]);
    st.insert(l[i] - 1);
    st.insert(l[i] + 1);
    st.insert(r[i]);
    st.insert(r[i] - 1);
    st.insert(r[i] + 1);
  }
  int cnt = 0;
  for (set<long long>::iterator it = st.begin(); it != st.end(); it++)
    if (*it) {
      ++cnt;
      MP[*it] = cnt;
      lol[cnt] = *it;
    }
  build(1, 1, cnt);
  for (int i = 1; i <= n; i++) {
    if (t[i] == 1)
      t[i] = 1;
    else if (t[i] == 2)
      t[i] = -1;
    else
      t[i] = 2;
    update(1, 1, cnt, MP[l[i]], MP[r[i]], t[i]);
    long long pos = query(1, 1, cnt);
    cout << pos << endl;
  }
}