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 n, m;
long long a[500005], t[500005], x[500005], y[500005], st[1 << 21],
    lazy[1 << 21];
int lazyOnSt(int type, int node, int b, int e) {
  if (type == 0) return 0;
  if (type == 1) return e - b + 1;
  return e - b + 1 - st[node];
}
int lazyOnLazy(int type1, int type2) {
  if (type2 == -1) return type1;
  if (type1 == 0) return 0;
  if (type1 == 1) return 1;
  if (type2 == 0) return 1;
  if (type2 == 1) return 0;
  return -1;
}
void fix(int node, int b, int e) {
  if (lazy[node] == -1) return;
  st[node] = lazyOnSt(lazy[node], node, b, e);
  if (b != e) {
    lazy[node << 1] = lazyOnLazy(lazy[node], lazy[node << 1]);
    lazy[node << 1 | 1] = lazyOnLazy(lazy[node], lazy[node << 1 | 1]);
  }
  lazy[node] = -1;
}
void update(int node, int b, int e, int i, int j, int type) {
  fix(node, b, e);
  if (b > j || e < i) return;
  if (b >= i && e <= j) {
    st[node] = lazyOnSt(type, node, b, e);
    if (b != e) {
      lazy[node << 1] = lazyOnLazy(type, lazy[node << 1]);
      lazy[node << 1 | 1] = lazyOnLazy(type, lazy[node << 1 | 1]);
    }
  } else {
    update(node << 1, b, ((b + e) / 2), i, j, type);
    update(node << 1 | 1, ((b + e) / 2) + 1, e, i, j, type);
    st[node] = st[node << 1] + st[node << 1 | 1];
  }
}
int query(int node, int b, int e) {
  fix(node, b, e);
  fix(node << 1, b, ((b + e) / 2));
  fix(node << 1 | 1, ((b + e) / 2) + 1, e);
  if (b == e) {
    return b;
  }
  int missingl = (((b + e) / 2) - b + 1) - st[node << 1];
  int missingr = (e - ((b + e) / 2)) - st[node << 1 | 1];
  if (missingl)
    return query(node << 1, b, ((b + e) / 2));
  else
    return query(node << 1 | 1, ((b + e) / 2) + 1, e);
}
int main() {
  scanf("%lld", &m);
  n = 1;
  a[n] = 1;
  for (int i = 1; i <= m; i++) {
    scanf("%lld %lld %lld", &t[i], &x[i], &y[i]);
    a[++n] = x[i];
    a[++n] = y[i];
    a[++n] = x[i] + 1;
    a[++n] = y[i] + 1;
  }
  sort(a + 1, a + 1 + n);
  long long k = unique(a + 1, a + 1 + n) - (a + 1);
  n = k;
  n++;
  a[n] = a[n - 1] + 1;
  memset(lazy, -1, sizeof(lazy));
  int types[] = {0, 1, 0, 2};
  for (int i = 1; i <= m; i++) {
    int l = lower_bound(a + 1, a + 1 + n, x[i]) - (a);
    int r = lower_bound(a + 1, a + 1 + n, y[i]) - (a);
    update(1, 1, n, l, r, types[t[i]]);
    printf("%lld\n", a[query(1, 1, n)]);
  }
  return 0;
}