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 MAX = 2e4 + 10;
const int INF = INT_MAX / 2;
const int MAXLOG = 20;
const int MOD = 1e9 + 7;
struct segtree {
  segtree *left, *right;
  int lazy_add, lazy_inv, start, end, mid, out;
  segtree(int start, int end)
      : start(start), end(end), lazy_add(0), lazy_inv(0) {
    mid = (start + end) / 2;
    if (start == end) {
      left = right = NULL;
      out = 1;
    } else {
      left = new segtree(start, mid);
      right = new segtree(mid + 1, end);
      out = left->out + right->out;
    }
  }
  void propagate() {
    if (lazy_add) {
      if (lazy_add > 0)
        out = end - start + 1;
      else
        out = 0;
      if (lazy_inv) out = (end - start + 1) - out;
      if (left != right) {
        left->lazy_add = lazy_add;
        right->lazy_add = lazy_add;
        left->lazy_inv = lazy_inv;
        right->lazy_inv = lazy_inv;
      }
      lazy_add = lazy_inv = 0;
    }
    if (lazy_inv) {
      out = (end - start + 1) - out;
      if (left != right) {
        left->lazy_inv ^= 1;
        right->lazy_inv ^= 1;
      }
      lazy_inv = 0;
    }
  }
  void update(int l, int r, int x) {
    propagate();
    if (start == l && end == r) {
      if (x == 1) lazy_add = -1, lazy_inv = 0;
      if (x == 2) lazy_add = 1, lazy_inv = 0;
      if (x == 3) lazy_inv ^= 1;
      propagate();
      return;
    }
    if (r <= mid)
      left->update(l, r, x);
    else if (l > mid)
      right->update(l, r, x);
    else
      left->update(l, mid, x), right->update(mid + 1, r, x);
    left->propagate();
    right->propagate();
    out = left->out + right->out;
  }
  int query() {
    propagate();
    if (start == end) return start;
    left->propagate();
    right->propagate();
    if (left->out > 0) return left->query();
    return right->query();
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<pair<int, pair<long long, long long> > > q(n);
  vector<long long> c;
  for (int i = 0; i < n; i++) {
    cin >> q[i].first >> q[i].second.first >> q[i].second.second;
    c.push_back(q[i].second.first);
    c.push_back(q[i].second.second);
    c.push_back(q[i].second.second + 1);
  }
  c.push_back(1);
  sort(c.begin(), c.end());
  c.resize(unique(c.begin(), c.end()) - c.begin());
  segtree st(0, c.size());
  for (int i = 0; i < n; i++) {
    int f = lower_bound(c.begin(), c.end(), q[i].second.first) - c.begin();
    int t = lower_bound(c.begin(), c.end(), q[i].second.second) - c.begin();
    st.update(f, t, q[i].first);
    int x = st.query();
    if (x == c.size())
      cout << c[x] + 1 << "\n";
    else
      cout << c[x] << "\n";
  }
}