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;
const int INF = 0x3f3f3f3f;
const long long llINF = 1e18;
const int MAXN = 3e5 + 5;
namespace FastIO {
char buf[1 << 23], *p1 = buf, *p2 = buf;
int read() {
  static int x, f;
  static char ch;
  x = 0, f = 1;
  ch = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
            ? EOF
            : *p1++);
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  return x * f;
}
long long readll() {
  static long long x, f;
  static char ch;
  x = 0, f = 1;
  ch = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
            ? EOF
            : *p1++);
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  while (isdigit(ch)) {
    x = (x << 1ll) + (x << 3ll) + (ch ^ 48);
    ch =
        (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  return x * f;
}
}  // namespace FastIO
using FastIO::read;
using FastIO::readll;
int n, Q;
long long a[MAXN];
struct Query {
  int type;
  long long l, r;
} q[MAXN];
namespace SegmentTree {
struct Tree {
  int l, r, len;
  int cov, rev, sum;
} tree[MAXN << 2];
void update(int k) { tree[k].sum = tree[k << 1].sum + tree[k << 1 | 1].sum; }
void applyCov(int k, int v) {
  tree[k].cov = v;
  tree[k].rev = 0;
  tree[k].sum = tree[k].len * v;
}
void applyRev(int k) {
  tree[k].cov != -1 ? tree[k].cov ^= 1 : tree[k].rev ^= 1;
  tree[k].sum = tree[k].len - tree[k].sum;
}
void down(int k) {
  if (tree[k].cov != -1) {
    applyCov(k << 1, tree[k].cov);
    applyCov(k << 1 | 1, tree[k].cov);
    tree[k].cov = -1;
  }
  if (tree[k].rev) {
    applyRev(k << 1);
    applyRev(k << 1 | 1);
    tree[k].rev = 0;
  }
}
void Build(int k, int l, int r) {
  tree[k].l = l;
  tree[k].r = r;
  tree[k].len = r - l + 1;
  tree[k].sum = tree[k].rev = 0;
  tree[k].cov = -1;
  if (l == r) return;
  int mid = (l + r) >> 1;
  Build(k << 1, l, mid);
  Build(k << 1 | 1, mid + 1, r);
  update(k);
}
void Modify(int k, int l, int r, int type) {
  if (tree[k].l >= l && tree[k].r <= r) {
    if (type == 1)
      applyCov(k, 1);
    else if (type == 2)
      applyCov(k, 0);
    else if (type == 3)
      applyRev(k);
    return;
  }
  down(k);
  int mid = (tree[k].l + tree[k].r) >> 1;
  if (l <= mid) Modify(k << 1, l, r, type);
  if (r > mid) Modify(k << 1 | 1, l, r, type);
  update(k);
}
int Query(int k) {
  if (tree[k].l == tree[k].r) return tree[k].l;
  down(k);
  if (tree[k << 1].sum < tree[k << 1].len)
    return Query(k << 1);
  else
    return Query(k << 1 | 1);
}
}  // namespace SegmentTree
int main() {
  Q = read();
  a[++n] = 1;
  for (int i = 1; i <= Q; i++) {
    int t = read();
    long long l = readll(), r = readll();
    q[i] = (Query){t, l, r};
    a[++n] = l;
    a[++n] = r;
    a[++n] = r + 1;
  }
  sort(a + 1, a + 1 + n);
  n = unique(a + 1, a + 1 + n) - a - 1;
  SegmentTree::Build(1, 1, n);
  for (int i = 1; i <= Q; i++) {
    int l = lower_bound(a + 1, a + 1 + n, q[i].l) - a;
    int r = lower_bound(a + 1, a + 1 + n, q[i].r) - a;
    SegmentTree::Modify(1, l, r, q[i].type);
    printf("%lld\n", a[SegmentTree::Query(1)]);
  }
  return 0;
}