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;
template <class T>
inline T Max(register T a, register T b) {
  return a > b ? a : b;
}
template <class T>
inline T Min(register T a, register T b) {
  return a < b ? a : b;
}
static char ss[1 << 25], *A = ss, *B = ss;
int m, t, tot;
int cou[200005 << 2], lazy[200005 << 2];
long long rea[200005 << 1], le[200005 << 2][2];
int d[200005 << 2];
struct qus {
  int opt;
  long long l, r;
} q[200005];
struct node {
  long long data;
  int id;
} b[200005 << 1];
template <class T>
inline void read(T& x) {
  char ch =
      (A == B && (B = (A = ss) + fread(ss, 1, 1 << 17, stdin), A == B) ? EOF
                                                                       : *A++);
  x = 0;
  while (!isdigit(ch))
    ch = (A == B && (B = (A = ss) + fread(ss, 1, 1 << 17, stdin), A == B)
              ? EOF
              : *A++);
  while (isdigit(ch))
    x = (x << 3) + (x << 1) + (ch ^ 48),
    ch = (A == B && (B = (A = ss) + fread(ss, 1, 1 << 17, stdin), A == B)
              ? EOF
              : *A++);
}
inline bool cmp(const node n1, const node n2) { return n1.data < n2.data; }
inline void unq() {
  sort(b + 1, b + 1 + tot, cmp);
  ++t, rea[t] = 1;
  b[0].data = 1;
  for (register int i = (1); i <= (tot); ++i) {
    if (b[i].data != b[i - 1].data) ++t, rea[t] = b[i].data;
    int x = b[i].id;
    if (q[x].l == b[i].data) q[x].l = t;
    if (q[x].r == b[i].data) q[x].r = t;
  }
  rea[t + 1] = b[tot].data + 1;
}
void build(int l, int r, int rt) {
  cou[rt] = 0;
  le[rt][0] = rea[l];
  le[rt][1] = rea[r + 1];
  if (l == r) return;
  int mid = l + r >> 1, ln = rt << 1, rn = ln | 1;
  build(l, mid, ln), build(mid + 1, r, rn);
  if (rea[mid] + 1 == rea[mid + 1]) d[rt] = -1;
}
inline void pushdown(int rt, int ln, int rn, int l, int mid, int r) {
  if (cou[rt] != -1) {
    cou[ln] = cou[rn] = cou[rt];
    if (d[ln] != -1) d[ln] = cou[rt];
    if (d[rn] != -1) d[rn] = cou[rt];
    le[ln][0] = (cou[rt] ? rea[mid + 1] : rea[l]),
    le[ln][1] = (cou[rt] ? rea[l] : rea[mid + 1]);
    le[rn][0] = (cou[rt] ? rea[r + 1] : rea[mid + 1]),
    le[rn][1] = (cou[rt] ? rea[mid + 1] : rea[r + 1]);
    lazy[rt] = 0;
    return;
  }
  if (lazy[rt]) {
    if (cou[ln] != -1) cou[ln] ^= 1;
    lazy[ln] ^= 1;
    if (d[ln] != -1) d[ln] ^= 1;
    swap(le[ln][0], le[ln][1]);
    if (cou[rn] != -1) cou[rn] ^= 1;
    lazy[rn] ^= 1;
    if (d[rn] != -1) d[rn] ^= 1;
    swap(le[rn][0], le[rn][1]);
    lazy[rt] = 0;
  }
}
inline void pushup(int rt, int ln, int rn, int l, int mid, int r) {
  if (cou[ln] == cou[rn] && (d[rt] == -1 || d[rt] == cou[ln]))
    cou[rt] = cou[ln];
  else
    cou[rt] = -1;
  le[rt][0] =
      (le[ln][0] == rea[mid + 1] ? (d[rt] != 0 ? le[rn][0] : rea[mid] + 1)
                                 : le[ln][0]);
  le[rt][1] =
      (le[ln][1] == rea[mid + 1] ? (d[rt] == 1 ? rea[mid] + 1 : le[rn][1])
                                 : le[ln][1]);
}
void updata(int v, long long x, long long y, int l, int r, int rt) {
  if (x <= l && y >= r) {
    if (v < 2)
      cou[rt] = v, d[rt] = (d[rt] == -1 ? -1 : v),
      le[rt][0] = (cou[rt] ? rea[r + 1] : rea[l]),
      le[rt][1] = (cou[rt] ? rea[l] : rea[r + 1]);
    else {
      if (cou[rt] != -1) cou[rt] ^= 1;
      lazy[rt] ^= 1;
      if (d[rt] != -1) d[rt] ^= 1;
      swap(le[rt][0], le[rt][1]);
    }
    return;
  }
  int mid = l + r >> 1, ln = rt << 1, rn = ln | 1;
  pushdown(rt, ln, rn, l, mid, r);
  if (x <= mid) updata(v, x, y, l, mid, ln);
  if (y > mid) updata(v, x, y, mid + 1, r, rn);
  if (x <= mid && y > mid && d[rt] != -1) {
    if (v < 2)
      d[rt] = v;
    else
      d[rt] ^= 1;
  }
  pushup(rt, ln, rn, l, mid, r);
}
int main() {
  read(m);
  for (register int i = (1); i <= (m); ++i)
    read(q[i].opt), read(q[i].l), read(q[i].r), b[++tot] = (node){q[i].l, i},
                                                b[++tot] = (node){q[i].r, i};
  unq();
  build(1, t, 1);
  for (register int i = (1); i <= (m); ++i) {
    int opt = q[i].opt, l = q[i].l, r = q[i].r;
    if (opt == 1)
      updata(1, l, r, 1, t, 1);
    else if (opt == 2)
      updata(0, l, r, 1, t, 1);
    else
      updata(2, l, r, 1, t, 1);
    printf("%lld\n", le[1][0]);
  }
  return 0;
}