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 MAXN = 100005;
int n;
map<long long, int> m;
struct ST {
  struct node {
    int l, r, lz;
    bool MAX, MIN;
  } t[(MAXN * 3) << 2];
  void xxor(int x) {
    if (!t[x].MAX)
      t[x].MAX = t[x].MIN = 1;
    else if (t[x].MIN)
      t[x].MAX = t[x].MIN = 0;
  }
  void xorlz(int x) {
    if (t[x].lz >= 0 && t[x].lz <= 1)
      t[x].lz ^= 1;
    else if (t[x].lz == 2)
      t[x].lz = -1;
    else
      t[x].lz = 2;
  }
  void down(int x) {
    if (t[x].lz == -1) return;
    if (t[x].lz >= 0 && t[x].lz <= 1) {
      t[x << 1].MAX = t[x << 1].MIN = t[x << 1].lz = t[x].lz;
      t[x << 1 | 1].MAX = t[x << 1 | 1].MIN = t[x << 1 | 1].lz = t[x].lz;
    } else {
      xxor(x << 1);
      xxor(x << 1 | 1);
      xorlz(x << 1);
      xorlz(x << 1 | 1);
    }
    t[x].lz = -1;
  }
  void update(int x) {
    t[x].MIN = min(t[x << 1].MIN, t[x << 1 | 1].MIN);
    t[x].MAX = max(t[x << 1].MAX, t[x << 1 | 1].MAX);
  }
  void Build(int x, int l, int r) {
    t[x].l = l;
    t[x].r = r;
    t[x].MAX = t[x].MIN = t[x].lz = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    Build(x << 1, l, mid);
    Build(x << 1 | 1, mid + 1, r);
  }
  void Cover(int x, int l, int r, int val) {
    if (l <= t[x].l && t[x].r <= r) {
      t[x].MIN = t[x].MAX = t[x].lz = val;
      return;
    }
    down(x);
    int mid = (t[x].l + t[x].r) >> 1;
    if (l <= mid) Cover(x << 1, l, r, val);
    if (mid + 1 <= r) Cover(x << 1 | 1, l, r, val);
    update(x);
  }
  void Xor(int x, int l, int r) {
    if (l <= t[x].l && t[x].r <= r) {
      xxor(x);
      xorlz(x);
      return;
    }
    down(x);
    int mid = (t[x].l + t[x].r) >> 1;
    if (l <= mid) Xor(x << 1, l, r);
    if (mid + 1 <= r) Xor(x << 1 | 1, l, r);
    update(x);
  }
  int query(int x) {
    if (t[x].l == t[x].r) return t[x].l;
    down(x);
    if (!t[x << 1].MIN)
      return query(x << 1);
    else
      return query(x << 1 | 1);
  }
} st;
struct caozuo {
  int opt;
  long long l, r;
} s[MAXN];
long long dz[MAXN * 3], LSH[MAXN * 3], tot, lsh;
void Add(long long x) { dz[++tot] = x; }
int main() {
  scanf("%d", &n);
  Add(1);
  for (int i = 1; i <= n; ++i) {
    scanf("%d %lld %lld", &s[i].opt, &s[i].l, &s[i].r);
    Add(s[i].l);
    Add(s[i].r);
    Add(s[i].r + 1);
  }
  sort(dz + 1, dz + tot + 1);
  for (int i = 1; i <= tot; ++i)
    if (dz[i] != dz[i - 1]) m[dz[i]] = ++lsh, LSH[lsh] = dz[i];
  st.Build(1, 1, lsh);
  for (int i = 1; i <= n; ++i) {
    if (s[i].opt <= 2)
      st.Cover(1, m[s[i].l], m[s[i].r], s[i].opt == 1 ? 1 : 0);
    else
      st.Xor(1, m[s[i].l], m[s[i].r]);
    printf("%lld\n", LSH[st.query(1)]);
  }
  return 0;
}