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;
template <typename T1, typename T2>
void Max(T1& a, T2 b) {
  a = max(a, (T1)b);
}
template <typename T1, typename T2>
void Min(T1& a, T2 b) {
  a = min(a, (T1)b);
}
struct STUpdate {
  STUpdate() : change(0) {}
  STUpdate(char ch) : change(ch) {}
  operator bool() { return change != 0; }
  void add(const STUpdate& update) {
    if (update.change == 1 || update.change == 2)
      change = update.change;
    else {
      change = 3 - change;
    }
  }
  char change;
};
struct STNode {
  STNode() : v(0) {}
  void combine(const STNode& a) { v += a.v; }
  void applyUpdate(int rangesize, const STUpdate& update) {
    if (update.change == 1)
      v = rangesize;
    else if (update.change == 2)
      v = 0;
    else
      v = rangesize - v;
  }
  int v;
};
const int N = 200001;
STNode st[N * 2];
STUpdate lazy[N];
int n;
int height;
int hsb_loc(int n) { return 31 - __builtin_clz(n); }
void build_tree() {
  height = hsb_loc(n) + 1;
  for (int i = n - 1; i > 0; i--) {
    st[i] = st[i << 1];
    st[i].combine(st[i << 1 | 1]);
  }
}
void clear_update() {
  for (int i = 1; i < n; i++) {
    lazy[i] = STUpdate();
  }
}
void push(int p) {
  for (int s = height, k = 1 << (height - 1); s > 1; --s, k >>= 1) {
    int i = p >> s;
    if (lazy[i]) {
      lazy[i << 1].add(lazy[i]);
      st[i << 1].applyUpdate(k, lazy[i]);
      lazy[i << 1 | 1].add(lazy[i]);
      st[i << 1 | 1].applyUpdate(k, lazy[i]);
      lazy[i] = STUpdate();
    }
  }
  int i = p >> 1;
  if (lazy[i]) {
    st[i << 1].applyUpdate(1, lazy[i]);
    st[i << 1 | 1].applyUpdate(1, lazy[i]);
    lazy[i] = STUpdate();
  }
}
STNode query_tree(int l, int r) {
  l += n;
  r += n;
  push(l);
  push(r);
  STNode ret;
  for (; l <= r; l >>= 1, r >>= 1) {
    if (l & 1) {
      ret.combine(st[l++]);
    }
    if (!(r & 1)) {
      ret.combine(st[r--]);
    }
  }
  return ret;
}
void update_tree(int l, int r, const STUpdate& update) {
  l += n;
  r += n;
  push(l);
  push(r);
  int l0 = l, r0 = r;
  if (l & 1) {
    st[l++].applyUpdate(1, update);
  }
  if (!(r & 1)) {
    st[r--].applyUpdate(1, update);
  }
  l >>= 1;
  r >>= 1;
  for (int k = 2; l <= r; l >>= 1, r >>= 1, k <<= 1) {
    if (l & 1) {
      st[l].applyUpdate(k, update);
      lazy[l++].add(update);
    }
    if (!(r & 1)) {
      st[r].applyUpdate(k, update);
      lazy[r--].add(update);
    }
  }
  while (!(l0 & 1)) l0 >>= 1;
  while (l0 > 1) {
    l0 >>= 1;
    st[l0] = st[l0 << 1];
    st[l0].combine(st[l0 << 1 | 1]);
  }
  while (r0 & 1) r0 >>= 1;
  while (r0 > 1) {
    r0 >>= 1;
    st[r0] = st[r0 << 1];
    st[r0].combine(st[r0 << 1 | 1]);
  }
}
struct GetID2 {
  map<long long, int> ids;
  vector<long long> values;
  void clear() {
    ids.clear();
    values.clear();
  }
  int size() const { return (int)values.size(); }
  template <typename T>
  int get(T&& x) {
    auto ret = ids.emplace(forward<T>(x), size());
    if (ret.second) values.push_back(ret.first->first);
    return ret.first->second;
  }
  long long getstr(int id) { return values[id]; }
};
long long l[N], r[N], t[N], a[N];
void solve() {
  long long m;
  cin >> m;
  a[0] = 1;
  for (int i = 0; i < (m); ++i) {
    cin >> t[i] >> l[i] >> r[i];
    r[i]++;
    a[i * 2 + 1] = l[i];
    a[i * 2 + 2] = r[i];
  }
  sort(a, a + 2 * m + 1);
  GetID2 ids;
  for (int i = 0; i < (2 * m + 1); ++i) ids.get(a[i]);
  n = ids.size();
  build_tree();
  for (int i = 0; i < (m); ++i) {
    update_tree(ids.get(l[i]), ids.get(r[i]) - 1, STUpdate(t[i]));
    long long lo = 0, hi = n - 1;
    while (lo <= hi) {
      long long mid = lo + hi >> 1;
      if (query_tree(lo, mid).v < mid - lo + 1)
        hi = mid - 1;
      else
        lo = mid + 1;
    }
    cout << ids.getstr(lo) << endl;
  }
}
void init() {}
int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  init();
  solve();
  return 0;
}