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 BLOCK = 450;
const int MAX_N = 202500;
struct Query {
  long long type, l, r;
};
int present[MAX_N];
int overwr[BLOCK];
int cnt[BLOCK];
void propagate(int i) {
  if (overwr[i] == 1) {
    for (int j = BLOCK * i; j < BLOCK * (i + 1); j++) {
      present[j] = 1;
    }
  } else if (overwr[i] == 2) {
    for (int j = BLOCK * i; j < BLOCK * (i + 1); j++) {
      present[j] = 0;
    }
  } else if (overwr[i] == 3) {
    for (int j = BLOCK * i; j < BLOCK * (i + 1); j++) {
      present[j] = !present[j];
    }
  }
  overwr[i] = 0;
}
void process(Query q) {
  q.r--;
  propagate(q.l / BLOCK);
  propagate(q.r / BLOCK);
  for (int i = q.l; i <= q.r;) {
    if (i % BLOCK == 0 && i + BLOCK <= q.r) {
      if (q.type == 1) {
        overwr[i / BLOCK] = 1;
        cnt[i / BLOCK] = BLOCK;
      } else if (q.type == 2) {
        overwr[i / BLOCK] = 2;
        cnt[i / BLOCK] = 0;
      } else if (q.type == 3) {
        overwr[i / BLOCK] = 3 - overwr[i / BLOCK];
        cnt[i / BLOCK] = BLOCK - cnt[i / BLOCK];
      }
      i += BLOCK;
    } else {
      if (q.type == 1) {
        cnt[i / BLOCK] += !present[i];
        present[i] = 1;
      } else if (q.type == 2) {
        cnt[i / BLOCK] -= present[i];
        present[i] = 0;
      } else if (q.type == 3) {
        if (present[i]) {
          cnt[i / BLOCK]--;
        } else {
          cnt[i / BLOCK]++;
        }
        present[i] = !present[i];
      }
      i++;
    }
  }
}
int mex() {
  for (int i = 0; i < BLOCK; i++) {
    if (cnt[i] != BLOCK) {
      propagate(i);
      for (int j = BLOCK * i; j < BLOCK * (i + 1); j++) {
        if (!present[j]) {
          return j;
        }
      }
    }
  }
  assert(false);
}
long long decomp[MAX_N];
int main() {
  ios::sync_with_stdio(false);
  int queryc;
  cin >> queryc;
  vector<Query> queries(queryc);
  map<long long, int> compr;
  for (int i = 0; i < queryc; i++) {
    cin >> queries[i].type >> queries[i].l >> queries[i].r;
    queries[i].r++;
    compr[queries[i].l] = 0;
    compr[queries[i].r] = 0;
  }
  compr[1] = 0;
  int cur = 0;
  for (map<long long, int>::iterator it = compr.begin(); it != compr.end();
       it++) {
    it->second = cur;
    cur++;
  }
  for (pair<long long, int> pr : compr) {
    decomp[pr.second] = pr.first;
  }
  for (int i = 0; i < queryc; i++) {
    queries[i].l = compr[queries[i].l];
    queries[i].r = compr[queries[i].r];
  }
  for (Query q : queries) {
    process(q);
    cout << decomp[mex()] << '\n';
  }
}