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 <class T, class S>
ostream& operator<<(ostream& os, const pair<T, S>& v) {
  return os << "(" << v.first << ", " << v.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "[";
  for (int i = int(0); i <= int((static_cast<int>((v).size())) - 1); ++i) {
    if (i) os << ", ";
    os << v[i];
  }
  return os << "]";
}
template <class T>
bool setmax(T& _a, T _b) {
  if (_a < _b) {
    _a = _b;
    return true;
  }
  return false;
}
template <class T>
bool setmin(T& _a, T _b) {
  if (_b < _a) {
    _a = _b;
    return true;
  }
  return false;
}
template <class T>
T gcd(T _a, T _b) {
  return _b == 0 ? _a : gcd(_b, _a % _b);
}
vector<int> read_vi(int n = -1) {
  if (n < 0) scanf("%d", &n);
  vector<int> a(n);
  for (int i = int(0); i <= int((n)-1); ++i) scanf("%d", &a[i]);
  return a;
}
vector<long long> read_vl(int n = -1) {
  if (n < 0) scanf("%d", &n);
  vector<long long> a(n);
  for (int i = int(0); i <= int((n)-1); ++i) scanf("%lld", &a[i]);
  return a;
}
vector<double> read_vd(int n = -1) {
  if (n < 0) scanf("%d", &n);
  vector<double> a(n);
  for (int i = int(0); i <= int((n)-1); ++i) scanf("%lf", &a[i]);
  return a;
}
vector<pair<int, int> > read_vpi(int n = -1) {
  if (n < 0) scanf("%d", &n);
  vector<pair<int, int> > a(n);
  for (int i = int(0); i <= int((n)-1); ++i)
    scanf("%d%d", &a[i].first, &a[i].second);
  return a;
}
vector<pair<long long, long long> > read_vpl(int n = -1) {
  if (n < 0) scanf("%d", &n);
  vector<pair<long long, long long> > a(n);
  for (int i = int(0); i <= int((n)-1); ++i)
    scanf("%lld%lld", &a[i].first, &a[i].second);
  return a;
}
vector<pair<double, double> > read_vpd(int n = -1) {
  if (n < 0) scanf("%d", &n);
  vector<pair<double, double> > a(n);
  for (int i = int(0); i <= int((n)-1); ++i)
    scanf("%lf%lf", &a[i].first, &a[i].second);
  return a;
}
inline long long powmod(long long a, long long b, long long m) {
  long long r = 1;
  for (; b > 0; b >>= 1, a = a * a % m) {
    if (b & 1) r = r * a % m;
  }
  return r;
}
class Set {
  struct Node {
    int ran, size;
    long long val;
    int l, r;
  } tr[800020];
  int root, cnt = 0;
  void update(int x) { tr[x].size = tr[tr[x].l].size + tr[tr[x].r].size + 1; }
  int lrotate(int x) {
    int y = tr[x].l;
    tr[x].l = tr[y].r, tr[y].r = x;
    update(x);
    return y;
  }
  int rrotate(int x) {
    int y = tr[x].r;
    tr[x].r = tr[y].l, tr[y].l = x;
    update(x);
    return y;
  }
  int insert(int x, long long val) {
    if (x == 0) {
      x = ++cnt;
      tr[x].ran = rand(), tr[x].val = val;
      tr[x].l = tr[x].r = 0;
    } else {
      if (val < tr[x].val) {
        tr[x].l = insert(tr[x].l, val);
        if (tr[tr[x].l].ran > tr[x].ran) x = lrotate(x);
      } else {
        tr[x].r = insert(tr[x].r, val);
        if (tr[tr[x].r].ran > tr[x].ran) x = rrotate(x);
      }
    }
    update(x);
    return x;
  }
  int remove(int x, long long val) {
    if (tr[x].val == val) {
      if (tr[x].l == 0 && tr[x].r == 0) return 0;
      if (tr[tr[x].l].ran > tr[tr[x].r].ran) {
        x = lrotate(x);
        tr[x].r = remove(tr[x].r, val);
      } else {
        x = rrotate(x);
        tr[x].l = remove(tr[x].l, val);
      }
    } else {
      if (val < tr[x].val) {
        tr[x].l = remove(tr[x].l, val);
      } else {
        tr[x].r = remove(tr[x].r, val);
      }
    }
    update(x);
    return x;
  }
  pair<int, long long> upper_bound(int x, long long val) const {
    if (x == 0) return {0, -1};
    if (val < tr[x].val) {
      return upper_bound(tr[x].l, val);
    } else {
      pair<int, long long> t = upper_bound(tr[x].r, val);
      setmax(t.second, tr[x].val);
      t.first += tr[tr[x].l].size + 1;
      return t;
    }
  }
  long long kth(int x, int k) const {
    assert(x > 0);
    int lsize = tr[tr[x].l].size;
    if (k < lsize) return kth(tr[x].l, k);
    if (k == lsize) return tr[x].val;
    return kth(tr[x].r, k - lsize - 1);
  }

 public:
  Set() {
    root = 0;
    tr[0].ran = -1, tr[0].size = 0;
    tr[0].l = tr[0].r = 0;
  }
  void insert(long long val) { root = insert(root, val); }
  void remove(long long val) { root = remove(root, val); }
  pair<int, long long> upper_bound(long long val) const {
    return upper_bound(root, val);
  }
  bool empty() const { return root == 0; }
  long long kth(int k) const { return kth(root, k); }
};
Set s;
int main() {
  const auto get = [&](long long i) { return s.upper_bound(i).first % 2; };
  const auto invert = [&](long long i) {
    if (s.upper_bound(i).second == i) {
      s.remove(i);
    } else {
      s.insert(i);
    }
  };
  const auto remove = [&](long long l, long long r) {
    while (1) {
      auto p = s.upper_bound(r);
      if (p.second >= l) {
        s.remove(p.second);
      } else {
        break;
      }
    }
  };
  int q;
  scanf("%d", &q);
  while (q--) {
    int t;
    long long l, r;
    scanf("%d%lld%lld", &t, &l, &r);
    if (t == 1 || t == 2) {
      int wanted = (t == 1 ? 1 : 0);
      long long p = get(r + 1);
      remove(l + 1, r);
      if (get(l) != wanted) invert(l);
      if (get(r + 1) != p) invert(r + 1);
    } else {
      invert(l), invert(r + 1);
    }
    long long ans = 1;
    if (!s.empty() && s.kth(0) == 1) {
      ans = s.kth(1);
    }
    printf("%lld\n", ans);
  }
  return 0;
}