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 JAVA):

Solution:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class CF817F_MEXQueries {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		TreeMap<Long, Integer> tm = new TreeMap<>();
		PriorityQueue<Long> pq = new PriorityQueue<>();
		mq[] queries = new mq[n];
		for (int i = 0; i < n; i++) {
			queries[i] = new mq(sc.nextInt(), sc.nextLong(), sc.nextLong());
			pq.add(queries[i].l);
			pq.add(queries[i].r);
		}
		int id = 1;
		tm.put(1l, id++);
		long[] arr = new long[n * 6 + 2];
		arr[1] = 1;
		while (!pq.isEmpty()) {
			if (pq.peek() > 1 && !tm.containsKey(pq.peek() - 1)) {
				arr[id] = pq.peek() - 1;
				tm.put(pq.peek() - 1, id++);
			}
			if (!tm.containsKey(pq.peek())) {
				arr[id] = pq.peek();
				tm.put(pq.peek(), id++);
			}
			if (!tm.containsKey(pq.peek() + 1)) {
				arr[id] = pq.peek() + 1;
				tm.put(pq.peek() + 1, id++);
			}
			pq.poll();
		}
		PrintWriter out = new PrintWriter(System.out);
		segmentTree st = new segmentTree(id);
		for (int i = 0; i < n; i++) {
			st.update(tm.get(queries[i].l), tm.get(queries[i].r), queries[i].v);
			out.println(arr[st.minQ()]);
		}
		out.flush();
		out.close();
	}

	static class mq {
		long l, r;
		int v;

		public mq(int vv, long ll, long rr) {
			l = ll;
			r = rr;
			v = vv;
		}
	}

	static class segmentTree {
		int[] st;
		int[] lazy; // holds 0 (not lazy) , 1 (add all), 2 (remove all)
					// 3 (invert all)
		int N;

		public segmentTree(int n) {
			N = 1;
			while (N < n)
				N <<= 1;
			st = new int[N << 1];
			lazy = new int[N << 1];
		}

		public void up(int id, int l, int r, int v) {
			if (v == 1)
				st[id] = r - l + 1;
			else if (v == 2)
				st[id] = 0;
			else
				st[id] = r - l + 1 - st[id];
			if (v == 3)
				lazy[id] = lazy[id] == 0 ? v : lazy[id] == 1 ? 2 : lazy[id] == 2 ? 1 : 0;
			else
				lazy[id] = v;

		}

		public void update(int i, int j, int v) {
			update(1, 1, N, i, j, v);
		}

		public void update(int id, int l, int r, int i, int j, int v) {
			if (i > r || j < l)
				return;
			int mid = (l + r) / 2;
			if (i <= l && r <= j) {
				up(id, l, r, v);
				return;
			}
			propagate(id << 1, l, mid);
			propagate(id << 1 | 1, mid + 1, r);
			propagate(id, l, r);
			update(id << 1, l, mid, i, j, v);
			update(id << 1 | 1, mid + 1, r, i, j, v);
			st[id] = st[id << 1] + st[id << 1 | 1];
		}

		public int minQ() {
			return minQ(1, 1, N);
		}

		public int minQ(int id, int l, int r) {
			if (l == r)
				return l;
			int mid = (l + r) / 2;
			propagate(id, l, r);
			if (st[id << 1] < mid - l + 1)
				return minQ(id << 1, l, mid);
			else
				return minQ(id << 1 | 1, mid + 1, r);
		}

		public void propagate(int id, int l, int r) {
			if (lazy[id] == 0 || l == r)
				return;
			int mid = (l + r) / 2;
			up(id << 1, l, mid, lazy[id]);
			up(id << 1 | 1, mid + 1, r, lazy[id]);
			lazy[id] = 0;
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public boolean nextEmpty() throws IOException {
			String s = nextLine();
			st = new StringTokenizer(s);
			return s.isEmpty();
		}
	}
}