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 long long MAXN = 3 * 100 * 1000 + 17, MAXS = 1e18;
vector<long long> all;
bool mark[MAXN << 2];
struct node {
  long long zer, one, lazy = 0;
  void toz(long long l) {
    one = all.size();
    zer = l;
  }
  void too(long long l) {
    one = l;
    zer = all.size();
  }
  void change(long long t, long long l) {
    if (t == 1)
      too(l), lazy = 1;
    else if (t == 2)
      toz(l), lazy = 2;
    else if (t == 3) {
      swap(one, zer);
      lazy = 3 - lazy;
    }
  }
};
int n;
node seg[MAXN << 2];
void assign(long long v, long long l, long long r) {
  if (!mark[v << 1]) {
    seg[v << 1].toz(l);
    seg[v << 1 | 1].toz(l + r >> 1);
    mark[v << 1] = true;
  }
}
void relax(long long v, long long l, long long r) {
  seg[v << 1].change(seg[v].lazy, l);
  seg[v << 1 | 1].change(seg[v].lazy, l + r >> 1);
  seg[v].lazy = 0;
}
void mrg(node &x, node &y, node &z) {
  x.zer = min(y.zer, z.zer);
  x.one = min(y.one, z.one);
}
void upd(long long type, long long lp, long long rp, long long v = 1,
         long long l = 1, long long r = all.size() + 1) {
  if (rp <= l || r <= lp) return;
  if (lp <= l && r <= rp) {
    seg[v].change(type, l);
    return;
  }
  assign(v, l, r);
  relax(v, l, r);
  upd(type, lp, rp, v << 1, l, l + r >> 1);
  upd(type, lp, rp, v << 1 | 1, l + r >> 1, r);
  mrg(seg[v], seg[v << 1], seg[v << 1 | 1]);
}
pair<long long, pair<long long, long long> > qr[MAXN];
void compress() {
  all.push_back(1);
  for (int i = 1; i <= n; i++)
    all.push_back(qr[i].second.first), all.push_back(qr[i].second.second),
        all.push_back(qr[i].second.second + 1);
  all.push_back(all.back() + 1);
  sort(all.begin(), all.end());
  all.resize(unique(all.begin(), all.end()) - all.begin());
  for (int i = 1; i <= n; i++)
    qr[i].second.first =
        lower_bound(all.begin(), all.end(), qr[i].second.first) - all.begin() +
        1,
    qr[i].second.second =
        lower_bound(all.begin(), all.end(), qr[i].second.second) - all.begin() +
        1;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  seg[1].toz(1);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    long long t, l, r;
    cin >> t >> l >> r;
    qr[i] = {t, {l, r}};
  }
  compress();
  for (int i = 1; i <= n; i++) {
    long long t = qr[i].first, l = qr[i].second.first, r = qr[i].second.second;
    upd(t, l, ++r);
    cout << all[seg[1].zer - 1] << '\n';
  }
  return 0;
}