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 MAXN = 200010, MAXQ = 100010;
struct Node {
  int l, r, cntZero;
  char tag, flag;
  Node *lc, *rc;
  void Cover(int k) {
    tag = k, flag = 0;
    cntZero = k ? 0 : r - l + 1;
  }
  void Flip() {
    flag ^= 1;
    cntZero = (r - l + 1) - cntZero;
  }
  void PushDown() {
    if (~tag) {
      lc->Cover(tag);
      rc->Cover(tag);
      tag = -1;
    }
    if (flag) {
      lc->Flip();
      rc->Flip();
      flag = 0;
    }
  }
  void Update() { cntZero = lc->cntZero + rc->cntZero; }
} pool[MAXN << 1], *cur = pool, *root;
int n, q, opt[MAXQ];
long long para1[MAXQ], para2[MAXQ], val[MAXN];
inline Node *AddNode(int l, int r) {
  cur->l = l, cur->r = r;
  cur->cntZero = r - l + 1;
  cur->tag = -1, cur->flag = 0;
  return cur++;
}
void Build(Node *&u, int l, int r) {
  u = AddNode(l, r);
  if (l == r) return;
  int mid = l + r >> 1;
  Build(u->lc, l, mid);
  Build(u->rc, mid + 1, r);
  u->Update();
}
void Assign(Node *u, int l, int r, int k) {
  if (l <= u->l && u->r <= r) {
    u->Cover(k);
    return;
  }
  u->PushDown();
  int mid = u->lc->r;
  if (l <= mid) Assign(u->lc, l, r, k);
  if (r > mid) Assign(u->rc, l, r, k);
  u->Update();
}
void Invert(Node *u, int l, int r) {
  if (l <= u->l && u->r <= r) {
    u->Flip();
    return;
  }
  u->PushDown();
  int mid = u->lc->r;
  if (l <= mid) Invert(u->lc, l, r);
  if (r > mid) Invert(u->rc, l, r);
  u->Update();
}
inline long long Query() {
  Node *u = root;
  while (u->l < u->r) {
    u->PushDown();
    if (u->lc->cntZero)
      u = u->lc;
    else
      u = u->rc;
  }
  return val[u->l];
}
inline void Init() {
  scanf("%d", &q);
  val[n++] = 1;
  for (int i = 0; i < q; ++i) {
    scanf("%d%I64d%I64d", &opt[i], &para1[i], &para2[i]);
    val[n++] = para1[i];
    val[n++] = para2[i] + 1;
  }
  sort(val, val + n);
  n = unique(val, val + n) - val;
  Build(root, 0, n - 1);
}
inline void Solve() {
  for (int i = 0; i < q; ++i) {
    int l = lower_bound(val, val + n, para1[i]) - val;
    int r = upper_bound(val, val + n, para2[i]) - val - 1;
    if (opt[i] == 1)
      Assign(root, l, r, 1);
    else if (opt[i] == 2)
      Assign(root, l, r, 0);
    else
      Invert(root, l, r);
    printf("%I64d\n", Query());
  }
}
int main() {
  Init();
  Solve();
  return 0;
}