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.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class MEXQueries { 

	static final int CLEAR = 1;
	static final int SET = 2;
	static final int FLIP = 3;

	static class Query {
		int type;
		long l, r;

		Query(int a, long b, long c) {
			type = a;
			l = b;
			r = c;
		}

		@Override
		public String toString() {
			return String.format("{%d, %d, %d}", type, l, r);
		}
	}

	static class SegmentTree {
		int N;
		int[] tree, lazy;

		int mid(int L, int R) {
			return (L + R) >> 1;
		}

		int left(int p) {
			return p << 1;
		}

		int right(int p) {
			return left(p) | 1;
		}

		SegmentTree(int n) {
			N = n;
			tree = new int[N << 2];
			lazy = new int[N << 2];
		}

		void propagate(int p, int L, int R) {
			if (L == R || lazy[p] == 0)
				return;
			int mid = mid(L, R), left = left(p), right = right(p);
			if (lazy[p] == SET) {
				tree[left] = (mid - L + 1);
				tree[right] = (R - mid);
				lazy[left] = lazy[p];
				lazy[right] = lazy[p];
			} else if (lazy[p] == CLEAR) {
				tree[left] = 0;
				tree[right] = 0;
				lazy[left] = lazy[p];
				lazy[right] = lazy[p];
			} else {
				tree[left] = (mid - L + 1) - tree[left];
				tree[right] = (R - mid) - tree[right];
				lazy[left] = lazy[left] == 0 ? FLIP : lazy[left] == SET ? CLEAR : lazy[left] == CLEAR ? SET : 0;
				lazy[right] = lazy[right] == 0 ? FLIP : lazy[right] == SET ? CLEAR : lazy[right] == CLEAR ? SET : 0;
			}
			lazy[p] = 0;
		}

		void set(int i, int j) {
			set(1, 1, N - 1, i, j);
		}

		void set(int p, int L, int R, int i, int j) {
			if (L > j || R < i)
				return;
			if (L >= i && R <= j) {
				tree[p] = (R - L + 1);
				lazy[p] = SET;
			} else {
				int mid = mid(L, R), left = left(p), right = right(p);
				propagate(p, L, R);
				set(left, L, mid, i, j);
				set(right, mid + 1, R, i, j);
				tree[p] = tree[left] + tree[right];
			}
		}

		void clear(int i, int j) {
			clear(1, 1, N - 1, i, j);
		}

		void clear(int p, int L, int R, int i, int j) {
			if (L > j || R < i)
				return;
			if (L >= i && R <= j) {
				tree[p] = 0;
				lazy[p] = CLEAR;
			} else {
				int mid = mid(L, R), left = left(p), right = right(p);
				propagate(p, L, R);
				clear(left, L, mid, i, j);
				clear(right, mid + 1, R, i, j);
				tree[p] = tree[left] + tree[right];
			}
		}

		void flip(int i, int j) {
			flip(1, 1, N - 1, i, j);
		}

		void flip(int p, int L, int R, int i, int j) {
			if (L > j || R < i)
				return;
			if (L >= i && R <= j) {
				tree[p] = (R - L + 1) - tree[p];
				lazy[p] = lazy[p] == 0 ? FLIP : lazy[p] == SET ? CLEAR : lazy[p] == CLEAR ? SET : 0;
			} else {
				int mid = mid(L, R), left = left(p), right = right(p);
				propagate(p, L, R);
				flip(left, L, mid, i, j);
				flip(right, mid + 1, R, i, j);
				tree[p] = tree[left] + tree[right];
			}
		}

		int query() {
			return query(1, 1, N - 1);
		}

		int query(int p, int L, int R) {
			if (L > R)
				return 0;
			if (L == R)
				return L;
			int mid = mid(L, R), left = left(p), right = right(p);
			propagate(p, L, R);
			if (tree[left] == mid - L + 1) {
				return query(right, mid + 1, R);
			}
			return query(left, L, mid);
		}
	}

	public static void main(String[] args) throws IOException {
		MyScanner sc = new MyScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt();
		Query[] q = new Query[n];
		TreeSet<Long> set = new TreeSet<>();
		for (int i = 0; i < n; i++) {
			int type = sc.nextInt();
			long l = sc.nextLong(), r = sc.nextLong();
			q[i] = new Query(type, l, r);
			set.add(l);
			set.add(r);
			set.add(l + 1);
			set.add(r + 1);
		}
		HashMap<Long, Integer> map = new HashMap<>();
		long[] unmap = new long[(q.length << 2) + 2];
		map.put(1L, 1);
		unmap[1] = 1;
		int idx = 2;
		for (Long x : set) {
			if (!map.containsKey(x)) {
				map.put(x, idx);
				unmap[idx++] = x;
			}
		}
		SegmentTree st = new SegmentTree(idx + 1);
		for (int i = 0; i < n; i++) {
			Query query = q[i];
			int l = map.get(query.l), r = map.get(query.r);
			if (query.type == 1) {
				st.set(l, r);
				out.println(unmap[st.query()]);
			} else if (query.type == 2) {
				st.clear(l, r);
				out.println(unmap[st.query()]);
			} else {
				st.flip(l, r);
				out.println(unmap[st.query()]);
			}
		}
		out.flush();
		out.close();
	}

	static class MyScanner {
		StringTokenizer st;
		BufferedReader br;

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

		public MyScanner(String file) throws IOException {
			br = new BufferedReader(new FileReader(new File(file)));
		}

		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 boolean ready() throws IOException {
			return br.ready();
		}
	}
}