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 = 400005;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-9;
template <class T>
inline void read(T &x) {
  int c;
  for (c = getchar(); c < 32 && ~c; c = getchar())
    ;
  for (x = 0; c > 32; x = x * 10 + c - '0', c = getchar())
    ;
}
template <class T>
struct Segtree {
  T data1[maxn << 2];
  T data2[maxn << 2];
  T lazy1[maxn << 2];
  T lazy2[maxn << 2];
  void pushup(int o) {
    data1[o] = min(data1[(o << 1)], data1[(o << 1) | 1]);
    data2[o] = max(data2[(o << 1)], data2[(o << 1) | 1]);
  }
  void setlazy1(int o, T v) {
    if (v == 2) {
      lazy1[o] = 2;
      data1[o] = 0;
      data2[o] = 0;
      lazy2[o] = 0;
      return;
    }
    lazy1[o] = v;
    data1[o] = v;
    data2[o] = v;
    lazy2[o] = 0;
  }
  void setlazy2(int o, T v) {
    lazy2[o] ^= 1;
    int t1 = 1, t2 = 0;
    if (data1[o] == 0) {
      t2 = 1;
    }
    if (data2[o] == 1) {
      t1 = 0;
    }
    data1[o] = t1;
    data2[o] = t2;
  }
  void pushdown(int o) {
    if (lazy1[o]) {
      setlazy1((o << 1), lazy1[o]);
      setlazy1((o << 1) | 1, lazy1[o]);
      lazy1[o] = 0;
    }
    if (lazy2[o]) {
      setlazy2((o << 1), lazy2[o]);
      setlazy2((o << 1) | 1, lazy2[o]);
      lazy2[o] = 0;
    }
  }
  void build(int o, int l, int r) {
    lazy1[o] = 0;
    lazy2[o] = 0;
    if (l == r) {
      data1[o] = 0;
      data2[o] = 0;
      return;
    }
    int mid = (l + r) >> 1;
    build((o << 1), l, mid);
    build((o << 1) | 1, mid + 1, r);
    pushup(o);
  }
  void update1(int o, int l, int r, int x, int y, T v) {
    if (l >= x && r <= y) {
      setlazy1(o, v);
      return;
    }
    pushdown(o);
    int mid = (l + r) >> 1;
    if (x <= mid) update1((o << 1), l, mid, x, y, v);
    if (y > mid) update1((o << 1) | 1, mid + 1, r, x, y, v);
    pushup(o);
  }
  void update2(int o, int l, int r, int x, int y, T v) {
    if (l >= x && r <= y) {
      setlazy2(o, v);
      return;
    }
    pushdown(o);
    int mid = (l + r) >> 1;
    if (x <= mid) update2((o << 1), l, mid, x, y, v);
    if (y > mid) update2((o << 1) | 1, mid + 1, r, x, y, v);
    pushup(o);
  }
  T query(int o, int l, int r, int x, int y) {
    if (l >= x && r <= y) {
      return data1[o];
    }
    pushdown(o);
    int mid = (l + r) >> 1;
    if (y <= mid) return query((o << 1), l, mid, x, y);
    if (x > mid) return query((o << 1) | 1, mid + 1, r, x, y);
    return min(query((o << 1), l, mid, x, y),
               query((o << 1) | 1, mid + 1, r, x, y));
  }
};
Segtree<long long> tree;
int n;
long long query[100005][4];
set<long long> st;
long long hash1[400005];
map<long long, int> mp;
int main() {
  read(n);
  for (int i = 0; i < n; i++) {
    read(query[i][0]);
    read(query[i][1]);
    read(query[i][2]);
    st.insert(query[i][1]);
    st.insert(query[i][2]);
    st.insert(query[i][1] + 1);
    st.insert(query[i][2] + 1);
  }
  st.insert(1);
  int ind = 1;
  for (auto &i : st) {
    hash1[ind] = i;
    mp[i] = ind;
    ind++;
  }
  hash1[ind] = hash1[ind - 1] + 1;
  tree.build(1, 1, ind);
  for (int i = 0; i < n; i++) {
    int l = mp[query[i][1]];
    int r = mp[query[i][2]];
    long long type = query[i][0];
    if (type == 1) {
      tree.update1(1, 1, ind, l, r, 1);
    } else if (type == 2) {
      tree.update1(1, 1, ind, l, r, 2);
    } else if (type == 3)
      tree.update2(1, 1, ind, l, r, 1);
    int _l = 1, _r = ind;
    while (_r - _l > 3) {
      int mid = (_l + _r) >> 1;
      if (tree.query(1, 1, ind, _l, mid) == 0) {
        _r = mid;
      } else if (tree.query(1, 1, ind, mid, _r) == 0) {
        _l = mid;
      } else
        break;
    }
    int tans = _l;
    for (; tans <= _r; tans++) {
      if (tree.query(1, 1, ind, tans, tans) == 0) {
        break;
      }
    }
    printf("%I64d\n", hash1[tans]);
  }
  return 0;
}