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>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
static char __allocator_space__[100000000];
static char *__sp = __allocator_space__;
template <typename T>
struct fastalloc : allocator<T> {
  fastalloc() {}
  template <typename T2>
  fastalloc(const fastalloc<T2> &a) {}
  template <typename T2>
  fastalloc<T> &operator=(const fastalloc<T2> &a) {
    return *this;
  }
  template <typename T2>
  struct rebind {};
  inline T *allocate(size_t n) {
    T *result = (T *)__sp;
    __sp += n * sizeof(T);
    return result;
  }
  inline void deallocate(T *p, size_t n) {}
};
struct chtholly_node {
  mutable long long l, r;
  mutable bool v;
  chtholly_node(long long L, long long R, bool x) : l(L), r(R), v(x) {}
  bool operator<(const chtholly_node &x) const { return l < x.l; }
};
long long ans = 1;
set<chtholly_node, less<chtholly_node>, fastalloc<chtholly_node> > chtholly;
typedef set<chtholly_node, less<chtholly_node>,
            fastalloc<chtholly_node> >::iterator IT;
inline IT chtholly_split(long long pos) {
  IT it = chtholly.lower_bound(chtholly_node(pos, -1, bool()));
  if (it != chtholly.end() && it->l == pos) return it;
  --it;
  long long L = it->l, R = it->r;
  bool V = it->v;
  chtholly.erase(it);
  chtholly.insert(chtholly_node(L, pos - 1, V));
  return chtholly.insert(chtholly_node(pos, R, V)).first;
}
inline void find_next() {
  IT it = chtholly_split(ans);
  while (true) {
    if (!it->v) {
      ans = it->l;
      return;
    }
    ++it;
  }
}
inline void chtholly_assign(long long l, long long r, bool x) {
  IT itr = chtholly_split(r + 1), itl = chtholly_split(l);
  chtholly.erase(itl, itr);
  chtholly.insert(chtholly_node(l, r, x));
  if (x == 0)
    ans = min(ans, l);
  else if (l <= ans && ans <= r)
    find_next();
}
void chtholly_reverse(long long l, long long r) {
  IT itr = chtholly_split(r + 1), itl = chtholly_split(l);
  if (l <= ans && ans <= r) {
    bool flag = false;
    for (; itl != itr; ++itl) {
      itl->v ^= 1;
      if (!flag && !itl->v) {
        flag = true;
        ans = itl->l;
      }
    }
    if (!flag) find_next();
  } else {
    bool flag = false;
    for (; itl != itr; ++itl) {
      itl->v ^= 1;
      if (!flag && !itl->v) {
        flag = true;
        ans = min(ans, itl->l);
      }
    }
  }
}
int q;
int main() {
  chtholly.insert(chtholly_node(1LL, 1000000000000000001LL, 0));
  scanf("%d", &q);
  while (q--) {
    int op;
    long long l, r;
    scanf("%d %lld %lld", &op, &l, &r);
    if (op == 1) chtholly_assign(l, r, 1);
    if (op == 2) chtholly_assign(l, r, 0);
    if (op == 3) chtholly_reverse(l, r);
    printf("%lld\n", ans);
  }
  return 0;
}