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>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  if (flag) x = -x;
}
using namespace std;
long long qtot;
struct query {
  long long type;
  long long l, r;
} q[601000];
long long h[601000], lsh_h[601000];
long long htot, ltot;
inline void lsh() {
  sort(h + 1, h + 1 + htot);
  h[htot + 1] = 3284782323424ll;
  for (register long long i = 1; i <= htot; ++i)
    if (h[i] && h[i] != h[i + 1]) lsh_h[++ltot] = h[i];
  for (register long long i = 1; i <= qtot; ++i) {
    q[i].l = lower_bound(lsh_h + 1, lsh_h + 1 + ltot, q[i].l) - lsh_h;
    q[i].r = lower_bound(lsh_h + 1, lsh_h + 1 + ltot, q[i].r) - lsh_h;
  }
}
long long ls[2401000], rs[2401000], tag[2401000], xr[2401000], root,
    len[2401000], sum[2401000], ttot;
inline void pushup(long long cur) { sum[cur] = sum[ls[cur]] + sum[rs[cur]]; }
inline void pusht(long long cur, long long tp) {
  if (!cur) return;
  tag[cur] = tp;
  sum[cur] = tag[cur] * len[cur];
  if (xr[cur]) xr[cur] = 0;
}
inline void pushxr(long long cur) {
  if (!cur) return;
  if (~tag[cur]) {
    tag[cur] ^= 1;
    sum[cur] = tag[cur] * len[cur];
    return;
  }
  sum[cur] = len[cur] - sum[cur];
  xr[cur] ^= 1;
}
inline void pushdown(long long cur) {
  if (~tag[cur])
    pusht(ls[cur], tag[cur]), pusht(rs[cur], tag[cur]), tag[cur] = -1;
  if (xr[cur]) pushxr(ls[cur]), pushxr(rs[cur]), xr[cur] = 0;
}
void build(long long L, long long R, long long &cur) {
  cur = ++ttot;
  len[cur] = R - L + 1;
  if (L == R) return;
  long long mid = (L + R) >> 1;
  build(L, mid, ls[cur]), build(mid + 1, R, rs[cur]);
  pushup(cur);
}
void Fuzhi(long long L, long long R, long long l, long long r, long long t,
           long long cur) {
  if (l <= L && R <= r) {
    pusht(cur, t);
    return;
  }
  pushdown(cur);
  long long mid = (L + R) >> 1;
  if (l <= mid) Fuzhi(L, mid, l, r, t, ls[cur]);
  if (r > mid) Fuzhi(mid + 1, R, l, r, t, rs[cur]);
  pushup(cur);
}
void modify(long long L, long long R, long long l, long long r, long long cur) {
  if (l <= L && R <= r) {
    pushxr(cur);
    return;
  }
  pushdown(cur);
  long long mid = (L + R) >> 1;
  if (l <= mid) modify(L, mid, l, r, ls[cur]);
  if (r > mid) modify(mid + 1, R, l, r, rs[cur]);
  pushup(cur);
}
inline void Query(long long L, long long R, long long cur) {
  if (L == R) {
    printf("%lld\n", lsh_h[L]);
    return;
  }
  pushdown(cur);
  long long mid = (L + R) >> 1;
  if (sum[ls[cur]] != len[ls[cur]])
    Query(L, mid, ls[cur]);
  else
    Query(mid + 1, R, rs[cur]);
}
signed main() {
  memset(tag, -1, sizeof(tag));
  read(qtot);
  for (register long long i = 1; i <= qtot; ++i) {
    long long t;
    long long l, r;
    read(t), read(l), read(r);
    q[i] = (query){t, l, r};
    h[++htot] = l - 1, h[++htot] = l, h[++htot] = l + 1;
    h[++htot] = r - 1, h[++htot] = r, h[++htot] = r + 1;
  }
  h[++htot] = 1;
  lsh();
  build(1, ltot, root);
  for (register long long i = 1; i <= qtot; ++i) {
    long long t = q[i].type, l = q[i].l, r = q[i].r;
    if (t == 1) {
      Fuzhi(1, ltot, l, r, 1, root);
    } else if (t == 2) {
      Fuzhi(1, ltot, l, r, 0, root);
    } else {
      modify(1, ltot, l, r, root);
    }
    Query(1, ltot, root);
  }
  return 0;
}