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;
int minn[800000][2], setv[800000];
bool rev[800000];
void build(int l, int r, int o) {
  setv[o] = -1;
  minn[o][0] = l;
  minn[o][1] = 0x7fffffff;
  if (l == r) return;
  int m = ((l + r) >> 1);
  build(l, m, o * 2);
  build(m + 1, r, o * 2 + 1);
}
void pushdown(int l, int r, int o) {
  int m = ((l + r) >> 1);
  if (setv[o] != -1) {
    int p = setv[o];
    setv[o * 2] = setv[o * 2 + 1] = p;
    rev[o * 2] = rev[o * 2 + 1] = 0;
    minn[o * 2][p] = l;
    minn[o * 2 + 1][p] = m + 1;
    minn[o * 2][p ^ 1] = minn[o * 2 + 1][p ^ 1] = 0x7fffffff;
    setv[o] = -1;
  }
  if (rev[o]) {
    rev[o * 2] ^= 1;
    rev[o * 2 + 1] ^= 1;
    swap(minn[o * 2][0], minn[o * 2][1]);
    swap(minn[o * 2 + 1][0], minn[o * 2 + 1][1]);
    rev[o] = 0;
  }
}
void update1(int l, int r, int o, int lx, int rx, int p) {
  if (l >= lx && r <= rx) {
    setv[o] = p;
    rev[o] = 0;
    minn[o][p] = l;
    minn[o][p ^ 1] = 0x7fffffff;
  } else {
    pushdown(l, r, o);
    int m = ((l + r) >> 1);
    if (m >= lx) update1(l, m, o * 2, lx, rx, p);
    if (m < rx) update1(m + 1, r, o * 2 + 1, lx, rx, p);
    minn[o][0] = min(minn[o * 2][0], minn[o * 2 + 1][0]);
    minn[o][1] = min(minn[o * 2][1], minn[o * 2 + 1][1]);
  }
}
void update2(int l, int r, int o, int lx, int rx) {
  if (l >= lx && r <= rx) {
    rev[o] ^= 1;
    swap(minn[o][0], minn[o][1]);
  } else {
    pushdown(l, r, o);
    int m = ((l + r) >> 1);
    if (m >= lx) update2(l, m, o * 2, lx, rx);
    if (m < rx) update2(m + 1, r, o * 2 + 1, lx, rx);
    minn[o][0] = min(minn[o * 2][0], minn[o * 2 + 1][0]);
    minn[o][1] = min(minn[o * 2][1], minn[o * 2 + 1][1]);
  }
}
struct Query {
  int kind;
  long long l, r;
  Query() {}
  Query(int a, long long b, long long c) : kind(a), l(b), r(c) {}
};
Query q[100005];
long long pos[200005];
int main() {
  int n;
  scanf("%d", &n);
  int tot = 0;
  for (int i = 1; i <= n; i++) {
    int x;
    long long y = 0, z = 0;
    scanf("%d%lld%lld", &x, &y, &z);
    q[i] = Query(x, y, z);
    pos[++tot] = y;
    pos[++tot] = z + 1;
  }
  pos[++tot] = 1;
  sort(pos + 1, pos + tot + 1);
  build(1, tot, 1);
  for (int i = 1; i <= n; i++) {
    int l = lower_bound(pos + 1, pos + tot + 1, q[i].l) - pos;
    int r = lower_bound(pos + 1, pos + tot + 1, q[i].r + 1) - pos - 1;
    if (q[i].kind == 1)
      update1(1, tot, 1, l, r, 1);
    else if (q[i].kind == 2)
      update1(1, tot, 1, l, r, 0);
    else
      update2(1, tot, 1, l, r);
    printf("%lld\n", pos[minn[1][0]]);
  }
  return 0;
}