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;
struct QuickIO {
  QuickIO() {
    const int SZ = 1 << 20;
    setvbuf(stdin, new char[SZ], _IOFBF, SZ);
    setvbuf(stdout, new char[SZ], _IOFBF, SZ);
  }
} QIO;
const int debug = 1;
const int INF = INT_MAX >> 1;
const int lc(int rt) { return rt << 1; }
const int rc(int rt) { return rt << 1 | 1; }
struct Node {
  int val, tag;
  int lb, rb;
} T[300000 * 4 + 10];
int root = 1;
void pushdown(int rt) {
  if (T[rt].lb == T[rt].rb) return;
  if (T[rt].tag == 1) {
    T[lc(rt)].val = T[lc(rt)].rb - T[lc(rt)].lb + 1;
    T[lc(rt)].tag = 1;
    T[rc(rt)].val = T[rc(rt)].rb - T[rc(rt)].lb + 1;
    T[rc(rt)].tag = 1;
  } else if (T[rt].tag == 2) {
    T[lc(rt)].val = 0;
    T[lc(rt)].tag = 2;
    T[rc(rt)].val = 0;
    T[rc(rt)].tag = 2;
  } else if (T[rt].tag == 3) {
    T[lc(rt)].val = (T[lc(rt)].rb - T[lc(rt)].lb + 1 - T[lc(rt)].val);
    T[lc(rt)].tag = 3 - T[lc(rt)].tag;
    T[rc(rt)].val = (T[rc(rt)].rb - T[rc(rt)].lb + 1 - T[rc(rt)].val);
    T[rc(rt)].tag = 3 - T[rc(rt)].tag;
  }
  T[rt].tag = 0;
}
void pushup(int rt) {
  if (T[rt].lb == T[rt].rb) return;
  T[rt].val = T[lc(rt)].val + T[rc(rt)].val;
}
void build(int l, int r, int rt) {
  T[rt].lb = l;
  T[rt].rb = r;
  T[rt].tag = 0;
  if (l == r)
    return;
  else {
    int mid = l + r >> 1;
    build(l, mid, lc(rt));
    build(mid + 1, r, rc(rt));
    pushup(rt);
  }
}
void update(int t, int l, int r, int rt) {
  if (l <= T[rt].lb && T[rt].rb <= r) {
    if (t == 1) {
      T[rt].val = (T[rt].rb - T[rt].lb + 1);
      T[rt].tag = 1;
    } else if (t == 2) {
      T[rt].val = 0;
      T[rt].tag = 2;
    } else {
      T[rt].val = (T[rt].rb - T[rt].lb + 1 - T[rt].val);
      T[rt].tag = 3 - T[rt].tag;
    }
  } else {
    pushdown(rt);
    int mid = T[rt].lb + T[rt].rb >> 1;
    if (l <= mid) {
      update(t, l, r, lc(rt));
    }
    if (mid < r) {
      update(t, l, r, rc(rt));
    }
    pushup(rt);
  }
}
int query(int rt) {
  if (T[rt].lb == T[rt].rb) return T[rt].lb;
  pushdown(rt);
  if (T[lc(rt)].rb - T[lc(rt)].lb + 1 == T[lc(rt)].val)
    return query(rc(rt));
  else
    return query(lc(rt));
}
struct Task {
  int t;
  long long l, r;
} task[100000 + 10];
long long hhashtable[300000 + 10];
int hlen;
void hhash() {
  sort(hhashtable, hhashtable + hlen);
  hlen = unique(hhashtable, hhashtable + hlen) - hhashtable;
}
int gethhashvalue(long long v) {
  return upper_bound(hhashtable, hhashtable + hlen, v) - hhashtable;
}
void init() {
  root = 1;
  hlen = 0;
}
int main() {
  init();
  int n;
  scanf("%d", &n);
  hhashtable[hlen++] = 1;
  for (int i = 0; i < n; i++) {
    scanf("%d%lld%lld", &task[i].t, &task[i].l, &task[i].r);
    hhashtable[hlen++] = task[i].l;
    hhashtable[hlen++] = task[i].r;
    hhashtable[hlen++] = task[i].r + 1;
  }
  hhash();
  build(1, hlen, root);
  for (int i = 0; i < n; i++) {
    int t = task[i].t;
    int l = gethhashvalue(task[i].l);
    int r = gethhashvalue(task[i].r);
    update(t, l, r, root);
    printf("%lld\n", hhashtable[query(root) - 1]);
  }
  return 0;
}