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;
inline long long getnum() {
  char c = getchar();
  long long num, sign = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') sign = -1;
  for (num = 0; c >= '0' && c <= '9';) {
    c -= '0';
    num = num * 10 + c;
    c = getchar();
  }
  return num * sign;
}
long long Q[100003][3];
long long A[400004];
int Tree[400004 * 4];
int Lazy[400004 * 4];
int Flip[400004 * 4];
void update(int l, int r, int ind, int lx, int rx, int val) {
  if (lx == l && rx == r) {
    if (val == 1) Tree[ind] = r - l + 1, Lazy[ind] = val, Flip[ind] = 0;
    if (val == 2) Tree[ind] = 0, Lazy[ind] = val, Flip[ind] = 0;
    if (val == 3) Tree[ind] = r - l + 1 - Tree[ind], Flip[ind] = 1 - Flip[ind];
    return;
  }
  int x = (l + r) / 2;
  if (Lazy[ind] || Flip[ind]) {
    if ((Lazy[ind] == 1 && !Flip[ind]) || (Lazy[ind] == 2 && Flip[ind])) {
      Tree[2 * ind] = x - l + 1;
      Tree[2 * ind + 1] = r - x;
      Lazy[2 * ind] = 1;
      Lazy[2 * ind + 1] = 1;
      Flip[2 * ind] = 0;
      Flip[2 * ind + 1] = 0;
    } else if ((Lazy[ind] == 2 && !Flip[ind]) ||
               (Lazy[ind] == 1 && Flip[ind])) {
      Tree[2 * ind] = 0;
      Tree[2 * ind + 1] = 0;
      Lazy[2 * ind] = 2;
      Lazy[2 * ind + 1] = 2;
      Flip[2 * ind] = 0;
      Flip[2 * ind + 1] = 0;
    } else if (Flip[ind]) {
      Tree[2 * ind] = x - l + 1 - Tree[2 * ind];
      Tree[2 * ind + 1] = r - x - Tree[2 * ind + 1];
      Flip[2 * ind] = 1 - Flip[2 * ind];
      Flip[2 * ind + 1] = 1 - Flip[2 * ind + 1];
    }
    Lazy[ind] = 0;
    Flip[ind] = 0;
  }
  if (rx <= x)
    update(l, x, 2 * ind, lx, rx, val);
  else if (lx > x)
    update(x + 1, r, 2 * ind + 1, lx, rx, val);
  else
    update(l, x, 2 * ind, lx, x, val),
        update(x + 1, r, 2 * ind + 1, x + 1, rx, val);
  Tree[ind] = Tree[2 * ind] + Tree[2 * ind + 1];
}
int getsum(int l, int r, int ind, int lx, int rx) {
  if (lx == l && rx == r) {
    return Tree[ind];
  }
  int x = (l + r) / 2;
  if (Lazy[ind] || Flip[ind]) {
    if ((Lazy[ind] == 1 && !Flip[ind]) || (Lazy[ind] == 2 && Flip[ind])) {
      Tree[2 * ind] = x - l + 1;
      Tree[2 * ind + 1] = r - x;
      Lazy[2 * ind] = 1;
      Lazy[2 * ind + 1] = 1;
      Flip[2 * ind] = 0;
      Flip[2 * ind + 1] = 0;
    } else if ((Lazy[ind] == 2 && !Flip[ind]) ||
               (Lazy[ind] == 1 && Flip[ind])) {
      Tree[2 * ind] = 0;
      Tree[2 * ind + 1] = 0;
      Lazy[2 * ind] = 2;
      Lazy[2 * ind + 1] = 2;
      Flip[2 * ind] = 0;
      Flip[2 * ind + 1] = 0;
    } else if (Flip[ind]) {
      Tree[2 * ind] = x - l + 1 - Tree[2 * ind];
      Tree[2 * ind + 1] = r - x - Tree[2 * ind + 1];
      Flip[2 * ind] = 1 - Flip[2 * ind];
      Flip[2 * ind + 1] = 1 - Flip[2 * ind + 1];
    }
    Lazy[ind] = 0;
    Flip[ind] = 0;
  }
  if (rx <= x)
    return getsum(l, x, 2 * ind, lx, rx);
  else if (lx > x)
    return getsum(x + 1, r, 2 * ind + 1, lx, rx);
  else
    return getsum(l, x, 2 * ind, lx, x) +
           getsum(x + 1, r, 2 * ind + 1, x + 1, rx);
}
int main() {
  int n = getnum(), ind = 0;
  for (int i = 1; i <= n; i++) {
    Q[i][2] = getnum(), Q[i][0] = getnum(), Q[i][1] = getnum();
    A[++ind] = Q[i][0];
    A[++ind] = Q[i][1];
    if (Q[i][0] > 1) A[++ind] = Q[i][0] - 1;
    A[++ind] = Q[i][1] + 1;
  }
  A[++ind] = 1;
  sort(A + 1, A + ind + 1);
  int lim = unique(A + 1, A + ind + 1) - A - 1;
  for (int i = 1; i <= n; i++) {
    int l = lower_bound(A + 1, A + lim + 1, Q[i][0]) - A;
    int r = lower_bound(A + 1, A + lim + 1, Q[i][1]) - A;
    int t = Q[i][2];
    update(1, lim, 1, l, r, t);
    int lx = 1, rx = lim;
    while (lx < rx) {
      int m = (lx + rx) / 2;
      int ans = getsum(1, lim, 1, 1, m);
      if (ans < m)
        rx = m;
      else
        lx = m + 1;
    }
    printf("%lld\n", A[rx]);
  }
}