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;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
template <class S, class T>
ostream& operator<<(ostream& os, const pair<S, T>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const unordered_set<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class S, class T>
ostream& operator<<(ostream& os, const unordered_map<S, T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class S, class T>
ostream& operator<<(ostream& os, const map<S, T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
void dbs(string str, T t) {
  cerr << str << " : " << t << "\n";
}
template <class T, class... S>
void dbs(string str, T t, S... s) {
  long long idx = str.find(',');
  cerr << str.substr(0, idx) << " : " << t << ",";
  dbs(str.substr(idx + 1), s...);
}
template <class T>
void prc(T a, T b) {
  cerr << "[";
  for (T i = a; i != b; ++i) {
    if (i != a) cerr << ", ";
    cerr << *i;
  }
  cerr << "]\n";
}
long long power(long long x, long long y) {
  long long res = 1;
  while (y) {
    if (y & 1) res = (res * x) % 1000000007;
    y = y / 2, x = (x * x) % 1000000007;
  }
  return res % 1000000007;
}
long long seg[16 * 100001];
long long lazy[16 * 100001];
void push(long long index, long long low, long long high) {
  if (lazy[index] == 1) {
    seg[index] = high - low + 1;
    if (low != high) {
      lazy[2 * index] = 1;
      lazy[2 * index + 1] = 1;
    }
  } else if (lazy[index] == 2) {
    seg[index] = 0;
    if (low != high) {
      lazy[2 * index] = 2;
      lazy[2 * index + 1] = 2;
    }
  } else {
    seg[index] = (high - low + 1 - seg[index]);
    if (low != high) {
      if (lazy[2 * index] == 0)
        lazy[2 * index] = 3;
      else if (lazy[2 * index] == 1)
        lazy[2 * index] = 2;
      else if (lazy[2 * index] == 2)
        lazy[2 * index] = 1;
      else
        lazy[2 * index] = 0;
      if (lazy[2 * index + 1] == 0)
        lazy[2 * index + 1] = 3;
      else if (lazy[2 * index + 1] == 1)
        lazy[2 * index + 1] = 2;
      else if (lazy[2 * index + 1] == 2)
        lazy[2 * index + 1] = 1;
      else
        lazy[2 * index + 1] = 0;
    }
  }
  lazy[index] = 0;
}
void update(long long index, long long low, long long high, long long l,
            long long r, long long val) {
  if (lazy[index]) {
    push(index, low, high);
  }
  if (low > r or high < l) return;
  if (low >= l and high <= r) {
    lazy[index] = val;
    push(index, low, high);
    return;
  }
  long long mid = (low + high) / 2;
  update(2 * index, low, mid, l, r, val);
  update(2 * index + 1, mid + 1, high, l, r, val);
  seg[index] = seg[2 * index + 1] + seg[2 * index];
}
long long answer(long long index, long long low, long long high) {
  if (lazy[index]) {
    push(index, low, high);
  }
  if (low == high) return low;
  long long mid = (low + high) / 2;
  if (lazy[2 * index]) push(2 * index, low, mid);
  if (seg[2 * index] <= mid - low) return answer(2 * index, low, mid);
  return answer(2 * index + 1, mid + 1, high);
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  vector<pair<long long, pair<long long, long long> > > query(n);
  set<long long> lol;
  map<long long, long long> haha;
  long long i;
  for (i = 0; i < n; i++) {
    cin >> query[i].first >> query[i].second.first >> query[i].second.second;
    lol.insert(query[i].second.first);
    lol.insert(query[i].second.first - 1);
    lol.insert(query[i].second.second);
    lol.insert(query[i].second.second + 1);
  }
  map<long long, long long> wow;
  lol.insert(1);
  long long cnt = 1;
  if (lol.find(0) != lol.end()) lol.erase(0);
  for (auto v : lol) haha[v] = cnt, wow[cnt] = v, cnt++;
  for (i = 0; i < n; i++) {
    update(1, 1, lol.size(), haha[query[i].second.first],
           haha[query[i].second.second], query[i].first);
    cout << wow[answer(1, 1, lol.size())] << "\n";
  }
}