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;
struct seg {
  long long tot;
  bool rev;
  int lazy;
  bool ro;
  seg *lson, *rson;
  seg() {}
  seg(int _rev) : rev(_rev) {
    lson = rson = NULL;
    lazy = -1;
    tot = 0;
    ro = false;
  }
  long long gettot() { return tot; }
  void pushup() {
    long long ret = 0;
    if (lson != NULL) ret += lson->gettot();
    if (rson != NULL) ret += rson->gettot();
    tot = ret;
  }
  int getid() { return lazy ^ rev; }
  void pushlazy(long long l, long long r) {
    long long mid = (l + r) >> 1;
    if (lson == NULL) lson = new seg(0);
    if (rson == NULL) rson = new seg(0);
    if (ro) {
      lson->rev ^= 1;
      lson->ro = !lson->ro;
      lson->tot = (mid - l + 1) - lson->tot;
      rson->rev ^= 1;
      rson->ro = !rson->ro;
      rson->tot = (r - (mid + 1) + 1) - rson->tot;
      ro = false;
    }
    if (lazy != -1) {
      lson->lazy = (getid() ^ lson->rev);
      lson->tot = (mid - l + 1) * lson->getid();
      rson->lazy = (getid() ^ rson->rev);
      rson->tot = (r - (mid + 1) + 1) * rson->getid();
      lazy = -1;
    }
  }
  void update(long long L, long long R, int val, bool we, long long l,
              long long r) {
    if (L <= l && r <= R) {
      if (!we) {
        lazy = val ^ rev;
        tot = (r - l + 1) * getid();
      } else {
        ro = !ro;
        rev ^= 1;
        tot = r - l + 1 - tot;
      }
      return;
    }
    pushlazy(l, r);
    long long mid = (l + r) >> 1;
    if (mid >= L) {
      lson->update(L, R, val, we, l, mid);
    }
    if (mid < R) {
      rson->update(L, R, val, we, mid + 1, r);
    }
    pushup();
  }
  long long query(long long l, long long r) {
    if (gettot() == 0) return l;
    long long mid = (l + r) >> 1;
    seg tmp = *this;
    pushlazy(l, r);
    if (lson->gettot() < (mid - l + 1))
      return lson->query(l, mid);
    else
      return rson->query(mid + 1, r);
  }
} * root;
const int MAXN = 1e5 + 5;
int tot;
long long Hash[MAXN * 4];
struct qu {
  int op;
  long long l, r;
} sv[MAXN];
int fi(long long now) {
  int ret = lower_bound(Hash, Hash + tot, now) - Hash;
  return ret;
}
int main() {
  root = new seg(0);
  tot = 0;
  Hash[tot++] = 1000000000000000001LL;
  Hash[tot++] = 1;
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int op;
    long long l, r;
    scanf("%d%lld%lld", &sv[i].op, &sv[i].l, &sv[i].r);
    Hash[tot++] = sv[i].l;
    Hash[tot++] = sv[i].r;
    if (sv[i].l != 1) Hash[tot++] = sv[i].l - 1;
    Hash[tot++] = sv[i].r + 1;
  }
  sort(Hash, Hash + tot);
  tot = unique(Hash, Hash + tot) - Hash;
  for (int i = 1; i <= n; i++) {
    sv[i].l = fi(sv[i].l);
    sv[i].r = fi(sv[i].r);
  }
  for (int i = 1; i <= n; i++) {
    if (sv[i].op == 1) {
      root->update(sv[i].l, sv[i].r, 1, false, 0, tot - 1);
    }
    if (sv[i].op == 2) {
      root->update(sv[i].l, sv[i].r, 0, false, 0, tot - 1);
    }
    if (sv[i].op == 3) {
      root->update(sv[i].l, sv[i].r, 0, true, 0, tot - 1);
    }
    int ret = root->query(0, tot - 1);
    long long ans;
    ans = Hash[ret];
    printf("%lld\n", ans);
  }
  return 0;
}