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 long long inf = 2e18;
struct segtree {
  vector<long long> l, r, m0, m1, tad;
  void ad(long long a, long long b, long long op, long long id) {
    if (b < l[id] || a > r[id]) return;
    if (a <= l[id] && b >= r[id]) {
      if (op == 1) {
        m0[id] = inf;
        m1[id] = l[id];
        tad[id] = 1;
      }
      if (op == 2) {
        m0[id] = l[id];
        m1[id] = inf;
        tad[id] = 2;
      }
      if (op == 3) {
        swap(m0[id], m1[id]);
        tad[id] = 3 - tad[id];
      }
      return;
    }
    prop(id);
    ad(a, b, op, 2 * id);
    ad(a, b, op, 2 * id + 1);
    pul(id);
  }
  void prop(long long id) {
    if (tad[id] != 0 && l[id] != r[id]) {
      ad(l[id], r[id], tad[id], 2 * id);
      ad(l[id], r[id], tad[id], 2 * id + 1);
    }
    tad[id] = 0;
  }
  void pul(long long id) {
    assert(l[id] != r[id]);
    m0[id] = min(m0[2 * id], m0[2 * id + 1]);
    m1[id] = min(m1[2 * id], m1[2 * id + 1]);
  }
  void qr(long long a, long long b, long long& tt, long long id) {
    if (b < l[id] || a > r[id]) return;
    if (a <= l[id] && b >= r[id]) {
      tt = min(tt, m0[id]);
      return;
    }
    prop(id);
    pul(id);
    qr(a, b, tt, 2 * id);
    qr(a, b, tt, 2 * id + 1);
  }
  void build(long long m) {
    long long rm = m;
    while (m & (m - 1)) ++m;
    l.clear();
    r.clear();
    tad.clear();
    m0.clear();
    m1.clear();
    l.resize(2 * m);
    r.resize(2 * m);
    tad.resize(2 * m, 0);
    m0.resize(2 * m, inf);
    for (long long i = 0; i < (m); ++i) {
      l[i + m] = r[i + m] = i;
    }
    for (long long i = m; i < m + rm; ++i) m0[i] = l[i];
    m1.resize(2 * m, inf);
    for (long long i = m - 1; i >= 1; --i) {
      m0[i] = min(m0[2 * i], m0[2 * i + 1]);
    }
    for (long long i = m - 1; i >= 1; --i) {
      l[i] = l[2 * i];
      r[i] = r[2 * i + 1];
    }
  }
};
segtree tr;
vector<long long> qtp, ql, qr;
map<long long, long long> prs;
map<long long, long long> enc;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long q;
  cin >> q;
  qtp.resize(q);
  ql.resize(q);
  qr.resize(q);
  prs[1] = 0;
  for (long long z = 0; z < (q); ++z) {
    cin >> qtp[z] >> ql[z] >> qr[z];
    prs[ql[z]] = 0;
    prs[qr[z] + 1] = 0;
  }
  long long nxt = 0;
  for (auto i = (prs).begin(); i != (prs).end(); ++i) {
    i->second = nxt;
    enc[nxt] = i->first;
    ++nxt;
  }
  tr.build(nxt);
  long long typ, l, r;
  for (long long z = 0; z < (q); ++z) {
    typ = qtp[z];
    l = prs[ql[z]];
    r = prs[qr[z] + 1] - 1;
    tr.ad(l, r, typ, 1);
    typ = inf;
    tr.qr(0, nxt - 1, typ, 1);
    assert(typ != inf);
    cout << enc[typ] << "\n";
  }
  return 0;
}