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;
map<long long, long long> old2new;
map<long long, long long> new2old;
long long n;
long long id[200000], st[200000], ed[200000];
long long SegTree[1500000], Tag[1500000];
long long sum;
void Xor(long long pos) {
  if (Tag[pos] == 1) {
    Tag[pos] = 2;
    return;
  }
  if (Tag[pos] == 2) {
    Tag[pos] = 1;
    return;
  }
  if (Tag[pos] == 0) {
    Tag[pos] = 3;
    return;
  }
  if (Tag[pos] == 3) Tag[pos] = 0;
}
void PushdownST(long long pos, long long l, long long r) {
  long long md = (l + r) / 2;
  if (Tag[pos] == 1) {
    Tag[2 * pos] = 1;
    Tag[2 * pos + 1] = 1;
    SegTree[2 * pos] = md - l + 1;
    SegTree[2 * pos + 1] = r - md;
  }
  if (Tag[pos] == 2) {
    Tag[2 * pos] = 2;
    Tag[2 * pos + 1] = 2;
    SegTree[2 * pos] = 0;
    SegTree[2 * pos + 1] = 0;
  }
  if (Tag[pos] == 3) {
    Xor(2 * pos);
    Xor(2 * pos + 1);
    SegTree[2 * pos] = md - l + 1 - SegTree[2 * pos];
    SegTree[2 * pos + 1] = r - md - SegTree[2 * pos + 1];
  }
  Tag[pos] = 0;
}
long long QueryST(long long pos, long long l, long long r) {
  PushdownST(pos, l, r);
  if (l == r) return l;
  long long ans = 0;
  long long md = (l + r) >> 1;
  if (SegTree[2 * pos] < md - l + 1)
    return QueryST(2 * pos, l, md);
  else
    return QueryST(2 * pos + 1, md + 1, r);
}
void PlUpdST(long long pos, long long l, long long r, long long a, long long b,
             long long command) {
  if (a <= l && r <= b) {
    if (l == r) {
      switch (command) {
        case 1:
          SegTree[pos] = 1;
          break;
        case 2:
          SegTree[pos] = 0;
          break;
        case 3:
          SegTree[pos] ^= 1;
          break;
      }
      return;
    }
    if (command == 1) {
      Tag[pos] = 1;
      SegTree[pos] = r - l + 1;
    }
    if (command == 2) {
      Tag[pos] = 2;
      SegTree[pos] = 0;
    }
    if (command == 3) {
      SegTree[pos] = r - l + 1 - SegTree[pos];
      Xor(pos);
    }
    return;
  }
  PushdownST(pos, l, r);
  long long md = (l + r) >> 1, ans = 0;
  if (a <= md) PlUpdST(2 * pos, l, md, a, b, command);
  if (b > md) PlUpdST(2 * pos + 1, md + 1, r, a, b, command);
  SegTree[pos] = SegTree[2 * pos] + SegTree[2 * pos + 1];
}
void lisanhua() {
  set<long long> a;
  for (long long i = 1; i <= n; i++) {
    a.insert(st[i]);
    a.insert(ed[i]);
    a.insert(ed[i] + 1);
  }
  a.insert(1);
  set<long long>::iterator i1 = a.begin();
  set<long long>::iterator i2 = a.end();
  long long i3 = 1;
  for (; i1 != i2; i1++) {
    old2new[*i1] = i3;
    new2old[i3] = *i1;
    i3++;
  }
  sum = i3 - 1;
}
int main() {
  cin >> n;
  for (long long i = 1; i <= n; i++) {
    cin >> id[i] >> st[i] >> ed[i];
  }
  lisanhua();
  for (long long i = 1; i <= n; i++) {
    PlUpdST(1, 1, sum, old2new[st[i]], old2new[ed[i]], id[i]);
    cout << new2old[QueryST(1, 1, sum)] << endl;
  }
}