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 maxm = 100005, maxk = maxm * 3, maxt = maxk << 2;
int m, tot, nums;
int o[maxm];
long long l[maxm], r[maxm], num[maxk], val[maxk];
map<long long, int> mp;
struct node {
  int lc, rc, fir0, fir1, lazy, tagxor;
} t[maxt];
inline void pushup(node &now, node a, node b) {
  now.fir0 = a.fir0 == -1 ? b.fir0 : a.fir0;
  now.fir1 = a.fir1 == -1 ? b.fir1 : a.fir1;
}
inline void getlazy(int l, int r, node &now, int v) {
  now.lazy = v, now.tagxor = -1;
  now.fir0 = v == 0 ? l : -1, now.fir1 = v == 1 ? l : -1;
}
inline void pushdown1(int l, int r, node &now) {
  if (now.lazy == -1) return;
  int mid = (l + r) >> 1;
  getlazy(l, mid, t[now.lc], now.lazy);
  getlazy(mid + 1, r, t[now.rc], now.lazy);
  now.lazy = -1;
}
inline void getxor(int l, int r, node &now) {
  pushdown1(l, r, now), now.tagxor ^= 1;
  swap(now.fir0, now.fir1);
}
inline void pushdown2(int l, int r, node &now) {
  if (now.tagxor == -1) return;
  int mid = (l + r) >> 1;
  getxor(l, mid, t[now.lc]), getxor(mid + 1, r, t[now.rc]);
  now.tagxor = -1;
}
inline void pushdown(int l, int r, node &now) {
  pushdown1(l, r, now), pushdown2(l, r, now);
}
void build(int l, int r, int now) {
  t[now].fir0 = l, t[now].fir1 = -1, t[now].lazy = -1, t[now].tagxor = -1;
  if (l == r) return;
  int mid = (l + r) >> 1;
  t[now].lc = now << 1, t[now].rc = now << 1 | 1;
  build(l, mid, t[now].lc), build(mid + 1, r, t[now].rc);
}
void update(int l, int r, int now, int L, int R, int v) {
  if (L <= l && r <= R) {
    getlazy(l, r, t[now], v);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(l, r, t[now]);
  if (L <= mid) update(l, mid, t[now].lc, L, R, v);
  if (mid < R) update(mid + 1, r, t[now].rc, L, R, v);
  pushup(t[now], t[t[now].lc], t[t[now].rc]);
}
void modify(int l, int r, int now, int L, int R) {
  if (L <= l && r <= R) {
    getxor(l, r, t[now]);
    return;
  }
  int mid = (l + r) >> 1;
  pushdown(l, r, t[now]);
  if (L <= mid) modify(l, mid, t[now].lc, L, R);
  if (mid < R) modify(mid + 1, r, t[now].rc, L, R);
  pushup(t[now], t[t[now].lc], t[t[now].rc]);
}
int main() {
  scanf("%d", &m);
  num[++nums] = 1;
  for (int i = 1; i <= m; i++) {
    scanf("%d%lld%lld", &o[i], &l[i], &r[i]);
    num[++nums] = l[i], num[++nums] = r[i], num[++nums] = r[i] + 1;
  }
  sort(num + 1, num + 1 + nums);
  for (int i = 1; i <= nums; i++)
    if (i == 1 || num[i] != num[i - 1])
      tot++, mp[num[i]] = tot, val[tot] = num[i];
  build(1, tot, 1);
  for (int i = 1; i <= m; i++) {
    if (o[i] == 1) update(1, tot, 1, mp[l[i]], mp[r[i]], 1);
    if (o[i] == 2) update(1, tot, 1, mp[l[i]], mp[r[i]], 0);
    if (o[i] == 3) modify(1, tot, 1, mp[l[i]], mp[r[i]]);
    printf("%lld\n", val[t[1].fir0]);
  }
  return 0;
}