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;
long long pwr(long long base, long long p, long long mod = (1000000007LL)) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = (ans * base) % mod;
    base = (base * base) % mod;
    p /= 2;
  }
  return ans;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long n, t[600005], l[600005], r[600005];
long long tree[6000005], lazy[6000005];
vector<long long> all;
map<long long, long long> m, revm;
void check(int node, int st, int en) {
  if (lazy[node] != -1) {
    if (lazy[node] == 2) {
      tree[node] = (en - st + 1) - tree[node];
      if (lazy[2 * node] == 2)
        lazy[2 * node] = -1;
      else if (lazy[2 * node] == -1)
        lazy[2 * node] = lazy[node];
      else
        lazy[2 * node] = lazy[2 * node] ^ 1;
      if (lazy[2 * node + 1] == 2)
        lazy[2 * node + 1] = -1;
      else if (lazy[2 * node + 1] == -1)
        lazy[2 * node + 1] = lazy[node];
      else
        lazy[2 * node + 1] = lazy[2 * node + 1] ^ 1;
    } else {
      tree[node] = (en - st + 1) * lazy[node];
      lazy[2 * node] = lazy[node];
      lazy[2 * node + 1] = lazy[node];
    }
    lazy[node] = -1;
  }
}
void update(int node, int st, int en, int p, int q, int val) {
  check(node, st, en);
  if (st > en || st > q || en < p) return;
  if (st >= p && en <= q) {
    lazy[node] = val;
    check(node, st, en);
    return;
  }
  int mid = (st + en) / 2;
  update(2 * node, st, mid, p, q, val);
  update(2 * node + 1, mid + 1, en, p, q, val);
  tree[node] = tree[2 * node] + tree[2 * node + 1];
}
int query(int node, int st, int en) {
  check(node, st, en);
  if (st > en) return st;
  int mid = (st + en) / 2;
  if (st == en) return st;
  check(2 * node, st, mid);
  check(2 * node + 1, mid + 1, en);
  int ans = 0;
  if (tree[2 * node] != (mid - st + 1))
    ans = query(2 * node, st, mid);
  else if (tree[2 * node + 1] != (en - mid))
    ans = query(2 * node + 1, mid + 1, en);
  else
    ans = en + 1;
  tree[node] = tree[2 * node] + tree[2 * node + 1];
  return ans;
}
int main() {
  scanf("%lld", &n);
  for (int i = 0; i < n; i++) {
    scanf("%lld %lld %lld", &t[i], &l[i], &r[i]);
    all.push_back(l[i]);
    all.push_back(r[i]);
    if (l[i] != 1) all.push_back(l[i] - 1);
    all.push_back(r[i] + 1);
  }
  sort(all.begin(), all.end());
  int total = 0;
  m[1] = 1;
  revm[1] = 1;
  total++;
  for (int i = 0; i < all.size(); i++) {
    if (!m[all[i]]) {
      total++;
      m[all[i]] = total;
      revm[total] = all[i];
    }
  }
  memset(lazy, -1, sizeof(lazy));
  for (int i = 0; i < n; i++) {
    if (t[i] == 1)
      update(1, 1, total, m[l[i]], m[r[i]], 1);
    else if (t[i] == 2)
      update(1, 1, total, m[l[i]], m[r[i]], 0);
    else
      update(1, 1, total, m[l[i]], m[r[i]], 2);
    int ans = query(1, 1, total);
    if (revm[ans] != 0)
      printf("%lld\n", revm[ans]);
    else
      printf("%d\n", ans);
  }
  return 0;
}