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;
namespace SGT {
int l[1200005];
int r[1200005];
int v[1200005];
int lazy[1200005];
void push_up(int now) { v[now] = v[(now << 1)] + v[((now << 1) | 1)]; }
void push_down(int now) {
  int lz = lazy[now];
  lazy[now] = -1;
  if (!~lz) return;
  if (lz == 2 and (lazy[(now << 1)] == 2 or lazy[(now << 1)] == -1))
    lazy[(now << 1)] = 1 - lazy[(now << 1)];
  if (lz == 2 and (lazy[((now << 1) | 1)] == 2 or lazy[((now << 1) | 1)] == -1))
    lazy[((now << 1) | 1)] = 1 - lazy[((now << 1) | 1)];
  if (lz == 2 and (lazy[(now << 1)] == 1 or lazy[(now << 1)] == 0))
    lazy[(now << 1)] ^= 1;
  if (lz == 2 and (lazy[((now << 1) | 1)] == 1 or lazy[((now << 1) | 1)] == 0))
    lazy[((now << 1) | 1)] ^= 1;
  if (lz < 2) lazy[(now << 1)] = lazy[((now << 1) | 1)] = lz;
  v[(now << 1)] = (lz == 2 ? (r[(now << 1)] - l[(now << 1)] + 1) - v[(now << 1)]
                           : lz * (r[(now << 1)] - l[(now << 1)] + 1));
  v[((now << 1) | 1)] =
      (lz == 2 ? (r[((now << 1) | 1)] - l[((now << 1) | 1)] + 1) -
                     v[((now << 1) | 1)]
               : lz * (r[((now << 1) | 1)] - l[((now << 1) | 1)] + 1));
}
void build(int now, int L, int R) {
  l[now] = L, r[now] = R, lazy[now] = -1;
  if (L == R) return void(v[now] = 0);
  build((now << 1), L, min(((l[now] + r[now]) >> 1), R));
  build(((now << 1) | 1), max(L, ((l[now] + r[now]) >> 1) + 1), R);
}
void modify(int now, int L, int R, int val) {
  if (l[now] == L and r[now] == R) {
    if (val == 2 and (lazy[now] == 2 or lazy[now] == -1))
      lazy[now] = 1 - lazy[now];
    if (val == 2 and (lazy[now] == 1 or lazy[now] == 0)) lazy[now] ^= 1;
    if (val < 2) lazy[now] = val;
    v[now] = (val == 2 ? (r[now] - l[now] + 1) - v[now]
                       : val * (r[now] - l[now] + 1));
    return;
  }
  push_down(now);
  if (L <= ((l[now] + r[now]) >> 1))
    modify((now << 1), L, min(((l[now] + r[now]) >> 1), R), val);
  if (R > ((l[now] + r[now]) >> 1))
    modify(((now << 1) | 1), max(L, ((l[now] + r[now]) >> 1) + 1), R, val);
  push_up(now);
}
int query(int now) {
  if (l[now] == r[now]) return l[now];
  push_down(now);
  if (v[(now << 1)] < (r[(now << 1)] - l[(now << 1)] + 1))
    return query((now << 1));
  return query(((now << 1) | 1));
}
}  // namespace SGT
namespace SPL {
vector<long long> Line;
auto Uend = Line.end();
void push(long long x) { Line.push_back(x); }
void init() {
  sort(Line.begin(), Line.end());
  Uend = unique(Line.begin(), Line.end());
}
int size() { return Uend - Line.begin() + 1; }
int rank(long long x) {
  return lower_bound(Line.begin(), Uend, x) - Line.begin() + 1;
}
long long order(int x) { return x <= size() ? Line[x - 1] : 1; }
}  // namespace SPL
long long que[100005][3];
void get(int x) {
  cin >> que[x][0] >> que[x][1] >> que[x][2];
  SPL::push(que[x][1]);
  SPL::push(que[x][2]);
  SPL::push(que[x][2] + 1);
  que[x][0]--;
  if (que[x][0] <= 1) que[x][0] ^= 1;
}
int main() {
  int m;
  cin >> m;
  for (int i = 1; i <= m; i++) get(i);
  SPL::Line.push_back(1);
  SPL::init();
  SGT::build(1, 1, SPL::size());
  for (int i = 1; i <= m; i++) {
    int x = SPL::rank(que[i][1]);
    int y = SPL::rank(que[i][2]);
    SGT::modify(1, x, y, que[i][0]);
    int rk = SGT::query(1);
    cout << SPL::order(rk) << "\n";
  }
  return 0;
}