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 maxn = 150020;
int m, cnt;
long long s[maxn << 2], n;
long long ll[maxn], rr[maxn];
int type[maxn];
map<long long, int> mp;
struct node {
  int sum, laz1, laz2;
} tr[maxn << 4];
inline long long read() {
  long long s = 0, w = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * w;
}
inline void update(int k) { tr[k].sum = tr[k << 1].sum + tr[k << 1 | 1].sum; }
inline void down(int k, int l, int r) {
  if (tr[k].laz1 == 1) {
    tr[k << 1].sum = ((l + r) >> 1) - l + 1;
    tr[k << 1].laz1 = 1;
    tr[k << 1].laz2 = 0;
    tr[k << 1 | 1].sum = r - ((l + r) >> 1);
    tr[k << 1 | 1].laz1 = 1;
    tr[k << 1 | 1].laz2 = 0;
  }
  if (tr[k].laz1 == 2) {
    tr[k << 1].sum = 0;
    tr[k << 1].laz1 = 2;
    tr[k << 1].laz2 = 0;
    tr[k << 1 | 1].sum = 0;
    tr[k << 1 | 1].laz1 = 2;
    tr[k << 1 | 1].laz2 = 0;
  }
  if (tr[k].laz2) {
    tr[k << 1].sum = ((l + r) >> 1) - l + 1 - tr[k << 1].sum;
    if (tr[k << 1].laz1 == 1)
      tr[k << 1].laz1 = 2;
    else if (tr[k << 1].laz1 == 2)
      tr[k << 1].laz1 = 1;
    else
      tr[k << 1].laz2 ^= 1;
    tr[k << 1 | 1].sum = r - ((l + r) >> 1) - tr[k << 1 | 1].sum;
    if (tr[k << 1 | 1].laz1 == 1)
      tr[k << 1 | 1].laz1 = 2;
    else if (tr[k << 1 | 1].laz1 == 2)
      tr[k << 1 | 1].laz1 = 1;
    else
      tr[k << 1 | 1].laz2 ^= 1;
  }
  tr[k].laz2 = tr[k].laz1 = 0;
}
void change(int k, int l, int r, int x, int y, int opt) {
  if (l == x && y == r) {
    if (opt == 1)
      tr[k].sum = r - l + 1, tr[k].laz1 = 1, tr[k].laz2 = 0;
    else if (opt == 0)
      tr[k].sum = 0, tr[k].laz1 = 2, tr[k].laz2 = 0;
    else {
      tr[k].sum = r - l + 1 - tr[k].sum;
      if (tr[k].laz1 == 1)
        tr[k].laz1 = 2;
      else if (tr[k].laz1 == 2)
        tr[k].laz1 = 1;
      else
        tr[k].laz2 ^= 1;
    }
    return;
  }
  down(k, l, r);
  if (y <= ((l + r) >> 1))
    change(k << 1, l, ((l + r) >> 1), x, y, opt);
  else if (x > ((l + r) >> 1))
    change(k << 1 | 1, ((l + r) >> 1) + 1, r, x, y, opt);
  else
    change(k << 1, l, ((l + r) >> 1), x, ((l + r) >> 1), opt),
        change(k << 1 | 1, ((l + r) >> 1) + 1, r, ((l + r) >> 1) + 1, y, opt);
  update(k);
}
void ask(int k, int l, int r) {
  if (l == r) {
    printf("%lld\n", s[l]);
    return;
  }
  down(k, l, r);
  if (tr[k << 1].sum < ((l + r) >> 1) - l + 1)
    ask(k << 1, l, ((l + r) >> 1));
  else
    ask(k << 1 | 1, ((l + r) >> 1) + 1, r);
}
int main() {
  m = read();
  for (int i = 1; i <= m; ++i) {
    type[i] = read();
    ll[i] = read();
    rr[i] = read() + 1;
    s[++cnt] = ll[i];
    s[++cnt] = rr[i];
  }
  s[++cnt] = 1;
  sort(s + 1, s + cnt + 1);
  n = unique(s + 1, s + cnt + 1) - s - 1;
  for (int i = 1; i <= n; ++i) mp[s[i]] = i;
  int opt, l, r;
  for (int i = 1; i <= m; ++i) {
    opt = type[i];
    l = mp[ll[i]];
    r = mp[rr[i]] - 1;
    if (opt == 1)
      change(1, 1, n, l, r, 1);
    else if (opt == 2)
      change(1, 1, n, l, r, 0);
    else
      change(1, 1, n, l, r, 2);
    ask(1, 1, n);
  }
  return 0;
}