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 N = 2e6;
long long t[4 * N];
long long fl[4 * N];
void push(long long ind, long long l, long long r) {
  if (fl[ind] == 1) {
    t[ind] = r - l + 1;
    if (l != r) {
      fl[ind * 2] = 1;
      fl[ind * 2 + 1] = 1;
    }
  }
  if (fl[ind] == -1) {
    t[ind] = 0;
    if (l != r) {
      fl[ind * 2] = -1;
      fl[ind * 2 + 1] = -1;
    }
  }
  if (fl[ind] == -2) {
    t[ind] = r - l + 1 - t[ind];
    if (l != r) {
      if (fl[ind * 2] == 0)
        fl[ind * 2] = -2;
      else if (fl[ind * 2] == 1)
        fl[ind * 2] = -1;
      else if (fl[ind * 2] == -2)
        fl[ind * 2] = 0;
      else
        fl[ind * 2] = 1;
      if (fl[ind * 2 + 1] == 0)
        fl[ind * 2 + 1] = -2;
      else if (fl[ind * 2 + 1] == 1)
        fl[ind * 2 + 1] = -1;
      else if (fl[ind * 2 + 1] == -2)
        fl[ind * 2 + 1] = 0;
      else
        fl[ind * 2 + 1] = 1;
    }
  }
  fl[ind] = 0;
}
void update(long long ind, long long l, long long r, long long i, long long j,
            long long ps) {
  if (fl[ind] != 0) push(ind, l, r);
  if (l == i && r == j) {
    fl[ind] = ps;
    return;
  }
  long long d = (r + l) / 2;
  if (j <= d)
    update(ind * 2, l, d, i, j, ps);
  else if (i >= d + 1)
    update(ind * 2 + 1, d + 1, r, i, j, ps);
  else {
    update(ind * 2, l, d, i, d, ps);
    update(ind * 2 + 1, d + 1, r, d + 1, j, ps);
  }
  push(ind * 2, l, d);
  push(ind * 2 + 1, d + 1, r);
  t[ind] = t[ind * 2] + t[ind * 2 + 1];
}
long long get(long long ind, long long l, long long r) {
  push(ind, l, r);
  if (l == r) {
    return l;
  }
  long long d = (r + l) / 2;
  push(ind * 2, l, d);
  push(ind * 2 + 1, d + 1, r);
  if (t[ind * 2] != d - l + 1)
    return get(ind * 2, l, d);
  else
    return get(ind * 2 + 1, d + 1, r);
}
void solve(vector<tuple<long long, long long, long long>> &a) {
  long long otv = 0, n = a.size();
  for (long long i = 0; i < n; i++) {
    auto [u, v, c] = a[i];
    for (long long j = 0; j < n; j++) {
      if (i == j) continue;
      auto [u1, v1, c1] = a[j];
      if (u1 > u && v1 > v && c1 > c) {
        otv++;
        break;
      }
    }
  }
  cout << otv << '\n';
  exit(0);
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ;
  long long n;
  cin >> n;
  vector<tuple<long long, long long, long long>> a(n);
  vector<long long> b(1, -1);
  ;
  b.push_back(1);
  for (long long i = 0; i < n; i++) {
    long long q, l, r;
    cin >> q >> l >> r;
    a[i] = {q, l, r};
    b.push_back(l);
    if (l != 1) b.push_back(l - 1);
    b.push_back(l + 1);
    b.push_back(r);
    if (r != 1) b.push_back(r - 1);
    b.push_back(r + 1);
  }
  sort(b.begin(), b.end());
  unordered_map<long long, long long> b2;
  unordered_map<long long, long long> b3;
  long long j = 1;
  for (long long i = 1; i < b.size(); i++) {
    if (b[i] == b[i - 1]) continue;
    b2[b[i]] = j;
    b3[j] = b[i];
    j++;
  }
  for (auto [q, l1, r1] : a) {
    long long l = b2[l1];
    long long r = b2[r1];
    if (q == 1) {
      update(1, 1, N, l, r, 1);
    }
    if (q == 2) {
      update(1, 1, N, l, r, -1);
    }
    if (q == 3) {
      update(1, 1, N, l, r, -2);
    }
    long long y = get(1, 1, N);
    cout << b3[y] << '\n';
  }
}