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 int N = 800010;
struct Node {
  Node *left = NULL, *right = NULL;
  long long value = 0;
  int lazy = 0;
} * root;
void prop(Node *at, long long i, long long j) {
  if (!at->lazy) return;
  if (at->lazy == 1) at->value = j - i + 1;
  if (at->lazy == 2) at->value = 0;
  if (at->lazy == 3) at->value = j - i + 1 - at->value;
  if (i != j) {
    if (at->left == NULL) at->left = new Node();
    if (at->lazy <= 2)
      at->left->lazy = at->lazy;
    else {
      if (at->left->lazy == 1)
        at->left->lazy = 2;
      else if (at->left->lazy == 2)
        at->left->lazy = 1;
      else if (at->left->lazy == 3)
        at->left->lazy = 0;
      else if (at->left->lazy == 0)
        at->left->lazy = 3;
    }
    if (at->right == NULL) at->right = new Node();
    if (at->lazy <= 2)
      at->right->lazy = at->lazy;
    else {
      if (at->right->lazy == 1)
        at->right->lazy = 2;
      else if (at->right->lazy == 2)
        at->right->lazy = 1;
      else if (at->right->lazy == 3)
        at->right->lazy = 0;
      else if (at->right->lazy == 0)
        at->right->lazy = 3;
    }
  }
  at->lazy = 0;
}
void update(Node *at, long long i, long long j, long long a, long long b,
            int lazy) {
  prop(at, i, j);
  if (i > b or j < a) return;
  if (i >= a and j <= b) {
    at->lazy = lazy;
    prop(at, i, j);
    return;
  }
  long long mid = (i + j) / 2;
  if (at->left == NULL) at->left = new Node();
  update(at->left, i, mid, a, b, lazy);
  if (at->right == NULL) at->right = new Node();
  update(at->right, mid + 1, j, a, b, lazy);
  at->value = at->left->value + at->right->value;
}
long long query(Node *at, long long i, long long j) {
  prop(at, i, j);
  if (i == j) return i;
  long long mid = (i + j) / 2;
  prop(at->left, i, mid);
  if (!at->left->value) return i;
  if (at->left->value != mid - i + 1) return query(at->left, i, mid);
  prop(at->right, mid + 1, j);
  if (!at->right->value) return mid + 1;
  return query(at->right, mid + 1, j);
}
long long q[N][3];
int main(void) {
  root = new Node();
  int n;
  scanf("%d", &n);
  vector<long long> v;
  for (int i = 0; i < n; i++) {
    int t;
    long long l, r;
    scanf("%d %lld %lld", &t, &l, &r);
    q[i][0] = t;
    q[i][1] = l;
    q[i][2] = r;
    v.push_back(l);
    v.push_back(r);
    if (l - 1) v.push_back(l - 1);
    if (r - 1) v.push_back(r - 1);
    v.push_back(l + 1);
    v.push_back(r + 1);
  }
  v.push_back(1);
  v.push_back(v.back() + 1);
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for (int i = 0; i < n; i++) {
    int t = q[i][0];
    int a = lower_bound(v.begin(), v.end(), q[i][1]) - v.begin();
    int b = lower_bound(v.begin(), v.end(), q[i][2]) - v.begin();
    update(root, 0, N, a, b, t);
    int k = query(root, 0, N);
    printf("%lld\n", v[k]);
  }
  return 0;
}