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 A, typename B>
ostream& operator<<(ostream& o, pair<A, B> a) {
  return o << a.first << ' ' << a.second;
}
template <typename A, typename B>
istream& operator>>(istream& o, pair<A, B>& a) {
  return o >> a.first >> a.second;
}
const int mod = 998244353, abc = 864197532, N = 100087, logN = 17, K = 333;
vector<long long int> v;
struct Seg {
  int l, r, m, val, lz1, lz2;
  Seg* ch[2];
  Seg(int _l, int _r) : l(_l), r(_r), m(l + r >> 1), val(0), lz1(-1), lz2(0) {
    if (r - l > 1) {
      ch[0] = new Seg(l, m);
      ch[1] = new Seg(m, r);
    }
  }
  void pull() { val = ch[0]->val + ch[1]->val; }
  void push() {
    if (r - l > 1 && ~lz1) {
      ch[0]->lz1 = lz1;
      ch[1]->lz1 = lz1;
      ch[0]->lz2 = 0;
      ch[1]->lz2 = 0;
      ch[0]->val = lz1 * (m - l);
      ch[1]->val = lz1 * (r - m);
      lz1 = -1;
    }
    if (r - l > 1 && lz2) {
      ch[0]->lz2 ^= lz2;
      ch[1]->lz2 ^= lz2;
      ch[0]->val = m - l - ch[0]->val;
      ch[1]->val = r - m - ch[1]->val;
      lz2 = 0;
    }
  }
  void add(int a, int b, int v) {
    if (a <= l && r <= b) {
      if (v == 2)
        lz2 ^= 1, val = r - l - val;
      else
        lz1 = v, lz2 = 0, val = lz1 * (r - l);
    } else {
      push();
      if (a < m) ch[0]->add(a, b, v);
      if (m < b) ch[1]->add(a, b, v);
      pull();
    }
  }
  int query() {
    if (r - l == 1) return l;
    push();
    if (ch[0]->val == m - l) return ch[1]->query();
    return ch[0]->query();
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int q;
  cin >> q;
  vector<pair<int, pair<long long int, long long int>>> Q(q);
  v.push_back(1);
  for (int i = 0; i < q; ++i)
    cin >> Q[i], Q[i].second.second++, v.push_back(Q[i].second.first),
        v.push_back(Q[i].second.second);
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  Seg root(0, v.size());
  for (int i = 0; i < q; ++i) {
    Q[i].second.first =
        lower_bound(v.begin(), v.end(), Q[i].second.first) - v.begin();
    Q[i].second.second =
        lower_bound(v.begin(), v.end(), Q[i].second.second) - v.begin();
    if (Q[i].first <= 2) Q[i].first = 3 - Q[i].first;
    root.add(Q[i].second.first, Q[i].second.second, Q[i].first - 1);
    cout << v[root.query()] << endl;
  }
}