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 = 300011;
const int INF = 0x7f7f7f7f;
int cases;
template <class T>
inline void read(T& x) {
  int c;
  for (c = getchar(); ~c && c < 33; c = getchar())
    ;
  for (x = 0; c > 32; x = x * 10 + c - '0', c = getchar())
    ;
}
struct Segtree {
  int data[MAXN << 2];
  int lazy[MAXN << 2];
  int flip[MAXN << 2];
  void pushup(int o) { data[o] = data[(o << 1)] + data[(o << 1) | 1]; }
  void setlazy(int o, int t, int v) {
    lazy[o] = v;
    data[o] = v * t;
    flip[o] = 0;
  }
  void setflip(int o, int t) {
    flip[o] ^= 1;
    data[o] = t - data[o];
  }
  void pushdown(int o, int m) {
    if (~lazy[o]) {
      setlazy((o << 1), m - (m >> 1), lazy[o]);
      setlazy((o << 1) | 1, m >> 1, lazy[o]);
      lazy[o] = -1;
    }
    if (flip[o]) {
      setflip((o << 1), m - (m >> 1));
      setflip((o << 1) | 1, m >> 1);
      flip[o] = 0;
    }
  }
  void build(int o, int l, int r) {
    lazy[o] = -1;
    flip[o] = 0;
    if (l == r) {
      data[o] = 0;
      return;
    }
    int mid = (l + r) >> 1;
    build((o << 1), l, mid);
    build((o << 1) | 1, mid + 1, r);
    pushup(o);
  }
  void update(int o, int l, int r, int x, int y, int v) {
    if (x <= l && r <= y) {
      setlazy(o, r - l + 1, v);
      return;
    }
    pushdown(o, r - l + 1);
    int mid = (l + r) >> 1;
    if (x <= mid) update((o << 1), l, mid, x, y, v);
    if (y > mid) update((o << 1) | 1, mid + 1, r, x, y, v);
    pushup(o);
  }
  void doflip(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
      setflip(o, r - l + 1);
      return;
    }
    pushdown(o, r - l + 1);
    int mid = (l + r) >> 1;
    if (x <= mid) doflip((o << 1), l, mid, x, y);
    if (y > mid) doflip((o << 1) | 1, mid + 1, r, x, y);
    pushup(o);
  }
  int query(int o, int l, int r) {
    if (l == r) {
      return l;
    }
    pushdown(o, r - l + 1);
    int mid = (l + r) >> 1;
    if (data[(o << 1)] == mid - l + 1) {
      return query((o << 1) | 1, mid + 1, r);
    }
    return query((o << 1), l, mid);
  }
} tree;
struct node {
  int o;
  long long x, y;
  node() {}
  node(int a, long long b, long long c) : o(a), x(b), y(c) {}
};
vector<node> v;
vector<long long> num;
int getid(long long x) {
  return 1 + distance(num.begin(), lower_bound(num.begin(), num.end(), x));
}
int main() {
  int n, op, l, r;
  long long x, y;
  read(n);
  while (n--) {
    read(op), read(x), read(y);
    v.emplace_back(op, x, y);
    num.emplace_back(x);
    num.emplace_back(y);
    num.emplace_back(y + 1);
  }
  num.emplace_back(1);
  sort(num.begin(), num.end());
  num.erase(unique(num.begin(), num.end()), num.end());
  int tot = num.size();
  tree.build(1, 1, tot);
  for (const auto& t : v) {
    op = t.o, l = getid(t.x), r = getid(t.y);
    if (op == 1) {
      tree.update(1, 1, tot, l, r, 1);
    } else if (op == 2) {
      tree.update(1, 1, tot, l, r, 0);
    } else {
      tree.doflip(1, 1, tot, l, r);
    }
    printf("%lld\n", num[tree.query(1, 1, tot) - 1]);
  }
}