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;
vector<long long> v;
long long n;
long long lo[4 * 200005 + 1], hi[4 * 200005 + 1], len[4 * 200005 + 1],
    cnt[4 * 200005 + 1], se[4 * 200005 + 1], flip[4 * 200005 + 1];
void update(long long i) {
  long long le, ri;
  if (se[2 * i] == -1)
    le = (flip[2 * i]) ? (len[2 * i] - cnt[2 * i]) : cnt[2 * i];
  else
    le = se[2 * i] * len[2 * i];
  if (se[2 * i + 1] == -1)
    ri = (flip[2 * i + 1]) ? (len[2 * i + 1] - cnt[2 * i + 1]) : cnt[2 * i + 1];
  else
    ri = se[2 * i + 1] * len[2 * i + 1];
  cnt[i] = le + ri;
}
void build(long long i, long long a, long long b) {
  lo[i] = a;
  hi[i] = b;
  if (a == b) {
    len[i] = 1;
    cnt[i] = 0;
    return;
  }
  long long m = (a + b) >> 1;
  build(2 * i, a, m);
  build(2 * i + 1, m + 1, b);
  len[i] = len[2 * i] + len[2 * i + 1];
}
void prop(long long i) {
  if (se[i] != -1) {
    se[2 * i] = se[2 * i + 1] = se[i];
    flip[2 * i] = flip[2 * i + 1] = 0;
    se[i] = -1;
  }
  if (flip[i]) {
    if (se[2 * i] == -1)
      flip[2 * i] = 1 - flip[2 * i];
    else
      se[2 * i] = 1 - se[2 * i];
    if (se[2 * i + 1] == -1)
      flip[2 * i + 1] = 1 - flip[2 * i + 1];
    else
      se[2 * i + 1] = 1 - se[2 * i + 1];
    flip[i] = 0;
  }
}
void change(long long i, long long a, long long b, long long val) {
  if (b < lo[i] || hi[i] < a) return;
  if (a <= lo[i] && hi[i] <= b) {
    se[i] = val;
    flip[i] = 0;
    return;
  }
  prop(i);
  change(2 * i, a, b, val);
  change(2 * i + 1, a, b, val);
  update(i);
}
void invert(long long i, long long a, long long b) {
  if (b < lo[i] || hi[i] < a) return;
  if (a <= lo[i] && hi[i] <= b) {
    if (se[i] != -1)
      se[i] = 1 - se[i];
    else
      flip[i] = 1 - flip[i];
    return;
  }
  prop(i);
  invert(2 * i, a, b);
  invert(2 * i + 1, a, b);
  update(i);
}
long long query(long long i) {
  long long ans;
  if (se[i] == -1)
    ans = (flip[i]) ? len[i] - cnt[i] : cnt[i];
  else
    ans = se[i] * len[i];
  if (ans == len[i]) return -1;
  if (lo[i] == hi[i]) {
    if (ans == 0)
      return v[lo[i]];
    else
      return -1;
  }
  prop(i);
  long long res = query(2 * i);
  if (res == -1) res = query(2 * i + 1);
  update(i);
  return res;
}
void solve() {
  cin >> n;
  long long t[n], a[n], b[n];
  for (long long i = 0; i < n; i++) {
    cin >> t[i] >> a[i] >> b[i];
    v.push_back(a[i]);
    v.push_back(b[i] + 1);
  }
  v.push_back(1);
  sort(v.begin(), v.end());
  auto ip = unique(v.begin(), v.end());
  v.resize(distance(v.begin(), ip));
  long long m = v.size();
  memset(se, -1, sizeof(se));
  build(1, 0, m - 1);
  for (long long i = 0; i < n; i++) {
    long long x = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
    long long y = lower_bound(v.begin(), v.end(), b[i] + 1) - v.begin() - 1;
    if (t[i] == 1)
      change(1, x, y, 1);
    else if (t[i] == 2)
      change(1, x, y, 0);
    else
      invert(1, x, y);
    cout << query(1) << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long tests = 1;
  while (tests--) {
    solve();
  }
  return 0;
}