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;
void _print() { cout << '\n'; }
template <typename T, typename... Ts>
void _print(const T& value, const Ts&... values) {
  cout << ' ' << value;
  _print(values...);
}
template <typename T, typename... Ts>
void print(const T& value, const Ts&... values) {
  cout << value;
  _print(values...);
}
const long long N = 4e5 + 10;
const long long INF = 1e18;
class ITrangeMaxMin {
 private:
  long long n, lazy[4 * N];
  pair<long long, long long> f[4 * N];
  long long merge(long long now, long long in) {
    if (now == 0) return in;
    if (now == 1) return (in == now ? 1 : 2);
    if (now == 2) return (in != now ? 1 : 2);
    if (in == 1 || in == 2) return in;
    return 0;
  }
  void dolazy(long long k, long long l, long long r) {
    if (lazy[k] == 0) return;
    if (lazy[k] == 1)
      f[k].first = f[k].second = 1;
    else if (lazy[k] == 2)
      f[k].first = f[k].second = 0;
    else {
      f[k].first ^= 1, f[k].second ^= 1;
      if (f[k].first > f[k].second) swap(f[k].first, f[k].second);
    }
    if (l != r) {
      lazy[k * 2] = merge(lazy[k * 2], lazy[k]);
      lazy[k * 2 + 1] = merge(lazy[k * 2 + 1], lazy[k]);
    }
    lazy[k] = 0;
  }
  void init(long long k, long long l, long long r) {
    f[k].first = f[k].second = lazy[k] = 0;
    if (l == r) return;
    init(k * 2, l, ((l + r) / 2));
    init(k * 2 + 1, ((l + r) / 2) + 1, r);
  }
  void update(long long k, long long l, long long r, long long L, long long R,
              long long val) {
    dolazy(k, l, r);
    if (r < L || R < l) return;
    if (L <= l && r <= R) {
      lazy[k] = merge(lazy[k], val);
      dolazy(k, l, r);
      return;
    }
    update(k * 2, l, ((l + r) / 2), L, R, val);
    update(k * 2 + 1, ((l + r) / 2) + 1, r, L, R, val);
    f[k].first = min(f[k * 2].first, f[k * 2 + 1].first);
    f[k].second = max(f[k * 2].second, f[k * 2 + 1].second);
  }
  long long get(long long k, long long l, long long r, long long pos) {
    dolazy(k, l, r);
    if (r < pos || pos < l) return -1;
    if (pos <= l && r <= pos) return f[k].first;
    return max(get(k * 2, l, ((l + r) / 2), pos),
               get(k * 2 + 1, ((l + r) / 2) + 1, r, pos));
  }
  long long find(long long k, long long l, long long r) {
    dolazy(k, l, r);
    if (f[k].first == 1) return -1;
    if (l == r) return l;
    auto rec = find(k * 2, l, ((l + r) / 2));
    if (rec != -1) return rec;
    return find(k * 2 + 1, ((l + r) / 2) + 1, r);
  }

 public:
  void init(long long _n) {
    n = _n;
    init(1, 0, n + 1);
  }
  long long find() { return find(1, 0, n + 1); }
  long long get(long long pos) { return get(1, 0, n + 1, pos); };
  void update(long long l, long long r, long long val) {
    update(1, 0, n + 1, l, r, val);
  };
} IT;
long long q;
vector<long long> all;
vector<tuple<long long, long long, long long> > query;
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> q;
  for (long long i = (1); i <= (q); i++) {
    long long type, l, r;
    cin >> type >> l >> r;
    for (long long j = (0); j <= (1); j++)
      all.push_back(l + j), all.push_back(r + j);
    query.push_back({type, l, r});
  }
  all.push_back(1);
  all.push_back(INF + 10);
  sort(all.begin(), all.end());
  all.resize(distance(all.begin(), unique(all.begin(), all.end())));
  IT.init(all.size());
  for (auto& [type, l, r] : query) {
    l = lower_bound(all.begin(), all.end(), l) - all.begin();
    r = lower_bound(all.begin(), all.end(), r) - all.begin();
    IT.update(l, r, type);
    auto rec = IT.find();
    long long ans = all[rec];
    cout << ans << '\n';
  }
}