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;
namespace IO {
void read(int &x) {
  x = 0;
  int f = 1;
  char c = getchar();
  while ('0' > c || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = (x << 3) + (x << 1) + c - '0';
    c = getchar();
  }
  x *= f;
}
void read(long long &x) {
  x = 0;
  int f = 1;
  char c = getchar();
  while ('0' > c || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = (x << 3) + (x << 1) + c - '0';
    c = getchar();
  }
  x *= f;
}
void write(int x) {
  if (x < 10)
    putchar(x + '0');
  else {
    write(x / 10);
    putchar(x % 10 + '0');
  }
}
void write(long long x) {
  if (x < 10)
    putchar(x + '0');
  else {
    write(x / 10);
    putchar(x % 10 + '0');
  }
}
}  // namespace IO
namespace lst {
struct node {
  int l, r;
  int col;
  int f;
} tre[2400005];
void build(int l, int r, int k) {
  tre[k].l = l;
  tre[k].r = r;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(l, mid, k << 1);
  build(mid + 1, r, k << 1 | 1);
}
void push_down(int k) {
  if (tre[k].col == -1 && tre[k].f == 0) return;
  if (tre[k].f) {
    if (tre[k << 1].col == -1)
      tre[k << 1].f ^= 1;
    else
      tre[k << 1].col ^= 1;
    if (tre[k << 1 | 1].col == -1)
      tre[k << 1 | 1].f ^= 1;
    else
      tre[k << 1 | 1].col ^= 1;
    tre[k].f = 0;
  } else {
    tre[k << 1].f = tre[k << 1 | 1].f = 0;
    tre[k << 1].col = tre[k << 1 | 1].col = tre[k].col;
  }
}
void update(int k) {
  if (tre[k << 1].col == tre[k << 1 | 1].col && tre[k << 1].col != -1)
    tre[k].col = tre[k << 1].col;
  else
    tre[k].col = -1;
}
void change(int l, int r, int val, int k = 1) {
  if (tre[k].l > r || l > tre[k].r) return;
  if (l <= tre[k].l && tre[k].r <= r) {
    tre[k].col = val;
    tre[k].f = 0;
    return;
  }
  push_down(k);
  change(l, r, val, k << 1);
  change(l, r, val, k << 1 | 1);
  update(k);
}
void reverse(int l, int r, int k = 1) {
  if (tre[k].l > r || l > tre[k].r) return;
  if (l <= tre[k].l && tre[k].r <= r) {
    if (tre[k].col != -1)
      tre[k].col ^= 1;
    else
      tre[k].f ^= 1;
    return;
  }
  push_down(k);
  reverse(l, r, k << 1);
  reverse(l, r, k << 1 | 1);
  update(k);
}
int find(int k = 1) {
  if (tre[k].l == tre[k].r) return tre[k].l;
  push_down(k);
  if (tre[k << 1].col != 1)
    return find(k << 1);
  else
    return find(k << 1 | 1);
}
void debug(int k = 1) {
  cout << tre[k].l << ' ' << tre[k].r << ' ' << tre[k].f << ' ' << tre[k].col
       << endl;
  if (tre[k].l == tre[k].r) return;
  push_down(k);
  debug(k << 1);
  debug(k << 1 | 1);
}
}  // namespace lst
using namespace IO;
using namespace lst;
struct NODE {
  int opt;
  long long l, r;
} a[100005];
int n;
int cnt = 0;
map<long long, int> f, hashh;
map<int, long long> unhashh;
int main() {
  read(n);
  for (int i = 1; i <= n; i++) {
    read(a[i].opt);
    read(a[i].l);
    read(a[i].r);
    f[a[i].l - 1] = f[a[i].l] = f[a[i].l + 1] = 1;
    f[a[i].r - 1] = f[a[i].r] = f[a[i].r + 1] = 1;
  }
  f[1] = 1;
  for (map<long long, int>::iterator it = f.begin(); it != f.end(); it++) {
    if ((*it).first == 0) continue;
    hashh[(*it).first] = ++cnt;
    unhashh[cnt] = (*it).first;
  }
  build(1, cnt, 1);
  for (int i = 1; i <= n; i++) {
    if (a[i].opt == 1) change(hashh[a[i].l], hashh[a[i].r], 1);
    if (a[i].opt == 2) change(hashh[a[i].l], hashh[a[i].r], 0);
    if (a[i].opt == 3) reverse(hashh[a[i].l], hashh[a[i].r]);
    write(unhashh[find()]);
    putchar('\n');
  }
  return 0;
}