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;
namespace fastIO {
bool IOerror = 0;
inline char nc() {
  static char buf[100005], *p1 = buf + 100005, *pend = buf + 100005;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 100005, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void read(int &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (sign) x = -x;
}
inline void read(long long &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (sign) x = -x;
}
inline void read(double &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (ch == '.') {
    double tmp = 1;
    ch = nc();
    for (; ch >= '0' && ch <= '9'; ch = nc())
      tmp /= 10.0, x += tmp * (ch - '0');
  }
  if (sign) x = -x;
}
inline void read(char *s) {
  char ch = nc();
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  for (; !blank(ch) && !IOerror; ch = nc()) *s++ = ch;
  *s = 0;
}
inline void read(char &c) {
  for (c = nc(); blank(c); c = nc())
    ;
  if (IOerror) {
    c = -1;
    return;
  }
}
inline void read1(int &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar())
    ;
  if (bo) x = -x;
}
inline void read1(long long &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar())
    ;
  if (bo) x = -x;
}
inline void read1(double &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar())
    ;
  if (ch == '.') {
    double tmp = 1;
    for (ch = getchar(); ch >= '0' && ch <= '9';
         tmp /= 10.0, x += tmp * (ch - '0'), ch = getchar())
      ;
  }
  if (bo) x = -x;
}
inline void read1(char *s) {
  char ch = getchar();
  for (; blank(ch); ch = getchar())
    ;
  for (; !blank(ch); ch = getchar()) *s++ = ch;
  *s = 0;
}
inline void read1(char &c) {
  for (c = getchar(); blank(c); c = getchar())
    ;
}
inline void read2(int &x) { scanf("%d", &x); }
inline void read2(long long &x) { scanf("%lld", &x); }
inline void read2(double &x) { scanf("%lf", &x); }
inline void read2(char *s) { scanf("%s", s); }
inline void read2(char &c) { scanf(" %c", &c); }
inline void readln2(char *s) { gets(s); }
struct Ostream_fwrite {
  char *buf, *p1, *pend;
  Ostream_fwrite() {
    buf = new char[100005];
    p1 = buf;
    pend = buf + 100005;
  }
  void out(char ch) {
    if (p1 == pend) {
      fwrite(buf, 1, 100005, stdout);
      p1 = buf;
    }
    *p1++ = ch;
  }
  void print(int x) {
    static char s[15], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
  }
  void println(int x) {
    static char s[15], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
    out('\n');
  }
  void print(long long x) {
    static char s[25], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
  }
  void println(long long x) {
    static char s[25], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
    out('\n');
  }
  void print(double x, int y) {
    static long long mul[] = {1,
                              10,
                              100,
                              1000,
                              10000,
                              100000,
                              1000000,
                              10000000,
                              100000000,
                              1000000000,
                              10000000000LL,
                              100000000000LL,
                              1000000000000LL,
                              10000000000000LL,
                              100000000000000LL,
                              1000000000000000LL,
                              10000000000000000LL,
                              100000000000000000LL};
    if (x < -1e-12) out('-'), x = -x;
    x *= mul[y];
    long long x1 = (long long)floor(x);
    if (x - floor(x) >= 0.5) ++x1;
    long long x2 = x1 / mul[y], x3 = x1 - x2 * mul[y];
    print(x2);
    if (y > 0) {
      out('.');
      for (size_t i = 1; i < y && x3 * mul[i] < mul[y]; out('0'), ++i)
        ;
      print(x3);
    }
  }
  void println(double x, int y) {
    print(x, y);
    out('\n');
  }
  void print(char *s) {
    while (*s) out(*s++);
  }
  void println(char *s) {
    while (*s) out(*s++);
    out('\n');
  }
  void flush() {
    if (p1 != buf) {
      fwrite(buf, 1, p1 - buf, stdout);
      p1 = buf;
    }
  }
  ~Ostream_fwrite() { flush(); }
} Ostream;
inline void print(int x) { Ostream.print(x); }
inline void println(int x) { Ostream.println(x); }
inline void print(char x) { Ostream.out(x); }
inline void println(char x) {
  Ostream.out(x);
  Ostream.out('\n');
}
inline void print(long long x) { Ostream.print(x); }
inline void println(long long x) { Ostream.println(x); }
inline void print(double x, int y) { Ostream.print(x, y); }
inline void println(double x, int y) { Ostream.println(x, y); }
inline void print(char *s) { Ostream.print(s); }
inline void println(char *s) { Ostream.println(s); }
inline void println() { Ostream.out('\n'); }
inline void flush() { Ostream.flush(); }
char Out[100005], *o = Out;
inline void print1(int x) {
  static char buf[15];
  char *p1 = buf;
  if (!x) *p1++ = '0';
  if (x < 0) *o++ = '-', x = -x;
  while (x) *p1++ = x % 10 + '0', x /= 10;
  while (p1-- != buf) *o++ = *p1;
}
inline void println1(int x) {
  print1(x);
  *o++ = '\n';
}
inline void print1(long long x) {
  static char buf[25];
  char *p1 = buf;
  if (!x) *p1++ = '0';
  if (x < 0) *o++ = '-', x = -x;
  while (x) *p1++ = x % 10 + '0', x /= 10;
  while (p1-- != buf) *o++ = *p1;
}
inline void println1(long long x) {
  print1(x);
  *o++ = '\n';
}
inline void print1(char c) { *o++ = c; }
inline void println1(char c) {
  *o++ = c;
  *o++ = '\n';
}
inline void print1(char *s) {
  while (*s) *o++ = *s++;
}
inline void println1(char *s) {
  print1(s);
  *o++ = '\n';
}
inline void println1() { *o++ = '\n'; }
inline void flush1() {
  if (o != Out) {
    if (*(o - 1) == '\n') *--o = 0;
    puts(Out);
  }
}
struct puts_write {
  ~puts_write() { flush1(); }
} _puts;
inline void print2(int x) { printf("%d", x); }
inline void println2(int x) { printf("%d\n", x); }
inline void print2(char x) { printf("%c", x); }
inline void println2(char x) { printf("%c\n", x); }
inline void print2(long long x) { printf("%lld", x); }
inline void println2(long long x) {
  print2(x);
  printf("\n");
}
inline void println2() { printf("\n"); }
};  // namespace fastIO
namespace tr {
int tot, val[1601000], laz[1601000];
void U(int x) { val[x] = val[x << 1] + val[x << 1 | 1]; }
void D(int x, int l, int mid, int r) {
  if (!laz[x] || l == r) {
    laz[x] = 0;
    return;
  }
  if (laz[x] == 1) {
    val[x << 1] = mid - l + 1;
    laz[x << 1] = 1;
    val[x << 1 | 1] = r - mid;
    laz[x << 1 | 1] = 1;
  } else if (laz[x] == 2) {
    val[x << 1] = 0;
    laz[x << 1] = 2;
    val[x << 1 | 1] = 0;
    laz[x << 1 | 1] = 2;
  } else {
    if (laz[x << 1] % 3) D(x << 1, l, l + mid >> 1, mid);
    val[x << 1] = mid - l + 1 - val[x << 1];
    laz[x << 1] ^= 3;
    if (laz[x << 1 | 1] % 3) D(x << 1 | 1, mid + 1, mid + 1 + r >> 1, r);
    val[x << 1 | 1] = r - mid - val[x << 1 | 1];
    laz[x << 1 | 1] ^= 3;
  }
  laz[x] = 0;
  U(x);
}
void C(int x, int l, int r, int st, int en, int ty) {
  int mid = l + r >> 1;
  D(x, l, mid, r);
  if (st > en) return;
  if (l == st && r == en) {
    if (ty == 1) {
      val[x] = r - l + 1;
    } else if (ty == 2) {
      val[x] = 0;
    } else {
      val[x] = r - l + 1 - val[x];
    }
    laz[x] = ty;
    return;
  }
  C(x << 1, l, mid, max(st, l), min(en, mid), ty);
  C(x << 1 | 1, mid + 1, r, max(st, mid + 1), min(en, r), ty);
  U(x);
}
int Q(int x, int l, int r) {
  int mid = l + r >> 1;
  D(x, l, mid, r);
  if (l == r) return l;
  if (val[x << 1] < mid - l + 1) return Q(x << 1, l, mid);
  return Q(x << 1 | 1, mid + 1, r);
}
void ccc(int st, int en, int ty) { C(1, 1, tot, st, en, ty); }
int que() { return Q(1, 1, tot); }
}  // namespace tr
int n, id;
map<long long, int> mp;
map<long long, int>::iterator it;
long long t[101000], l[101000], r[101000], to[404000];
void doit(int ty, int st, int en) {
  tr::ccc(st, en, ty);
  fastIO::println(to[tr::que()]);
}
int main() {
  fastIO::read(n);
  mp[1] = 1;
  for (int i = 1; i <= n; i++) {
    fastIO::read(t[i]);
    fastIO::read(l[i]);
    fastIO::read(r[i]);
    if (l[i] - 1) mp[l[i] - 1] = 1;
    mp[l[i]] = 1;
    mp[r[i]] = 1;
    mp[r[i] + 1] = 1;
  }
  for (it = mp.begin(); it != mp.end(); it++) {
    to[mp[it->first] = ++id] = it->first;
  }
  tr::tot = id;
  for (int i = 1; i <= n; i++) {
    doit(t[i], mp[l[i]], mp[r[i]]);
  }
}