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:
//package Chapter2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class Main {
//	static class pair {
//		int av;
//		long min;
//
//		public pair(int a, long min) {
//			this.min = min;
//			av = a;
//		}
//	}
	//
	// static class SegmentTree { // 1-based DS, OOP
	//
	// int N; // the number of elements in the array as a power of 2 (i.e. after
	// padding)
	// int[] array;
	// int[] setTime;
	// int[] clearTime;
	// int[] invertTime;
	// pair[] sTree;
	// TreeMap<Integer,Long> tm2;
	// SegmentTree(int N, TreeMap<Integer,Long> tm2) {
	//
	// this.N =N;
	// this.tm2 = tm2;
	// sTree = new pair[N << 1]; // no. of nodes = 2*N - 1, we add one to cross out
	// index zero
	// setTime = new int[N << 1];
	// invertTime = new int[N << 1];
	// clearTime = new int[N << 1];
	// build(1, 1, N);
	// }
	//
	// void build(int node, int b, int e) // O(n)
	// {// 0 if it is not available
	// if (b == e) {
	// if(tm2.containsKey(b))
	// sTree[node] = new pair(0, tm2.get(b));
	// else
	// sTree[node] = new pair(0, -1);
	// }
	// else {
	// int mid = b + e >> 1;
	// build(node << 1, b, mid);
	// build(node << 1 | 1, mid + 1, e);
	// pair left = sTree[node << 1];
	// pair right = sTree[node << 1 | 1];
	//
	// if (left.av == 1 && right.av == 1)
	// sTree[node] = new pair(1, left.min);
	// else if (right.av == 1)// if the left one is not available, I care about the
	// left one anyways
	// sTree[node] = new pair(0, left.min);
	// else if (left.av == 1)
	// sTree[node] = new pair(0, right.min);
	// else
	// sTree[node] = new pair(0, left.min);
	//
	// }
	// }
	//
	// // void update_point(int index, int val) // O(log n)
	// // {
	// // index += N - 1;
	// // sTree[index] += val;
	// // while (index > 1) {
	// // index >>= 1;
	// // sTree[index] = sTree[index << 1] + sTree[index << 1 | 1];
	// // }
	// // }
	//
	// void update_range(int i, int j, int time, int type) // O(log n)
	// {
	// update_range(1, 1, N, i, j, time, type);
	// }
	//
	// void update_range(int node, int b, int e, int i, int j, int time, int type) {
	// if (i > e || j < b)
	// return;
	// if (b >= i && e <= j) {
	// // now you are all available in that case I should not take your values into
	// // consideration
	// if (type == 1) {
	// sTree[node] = new pair(1, sTree[node].min);
	// setTime[node] = time;
	// } else if (type == 2) {
	// sTree[node] = new pair(0, sTree[node].min);
	// clearTime[node] = time;
	// } else {
	// sTree[node] = new pair(1 - sTree[node].av, sTree[node].min);
	// invertTime[node] = time;
	// }
	// } else {
	// int mid = b + e >> 1;
	// propagate(node, b, mid, e);
	// update_range(node << 1, b, mid, i, j, time,type);
	// update_range(node << 1 | 1, mid + 1, e, i, j, time,type);
	// pair left = sTree[node << 1];
	// pair right = sTree[node << 1 | 1];
	//// set is b-One
	// if (left.av == 1 && right.av == 1)//but not to be taken into consideration
	// sTree[node] = new pair(1, left.min);
	// else if (right.av == 1)// if the left one is not available, I care about the
	// left one anyways
	// sTree[node] = new pair(0, left.min);
	// else if (left.av == 1)
	// sTree[node] = new pair(0, right.min);
	// else
	// sTree[node] = new pair(0, left.min);
	//
	// }
	//
	// }
	//
	// void propagate(int node, int b, int mid, int e) {
	// invertTime[node << 1] = invertTime[node];
	// invertTime[node << 1| 1] = invertTime[node];
	// setTime[node << 1] = setTime[node];
	// setTime[node << 1| 1] = setTime[node];
	// clearTime[node << 1] = clearTime[node];
	// clearTime[node << 1| 1] = clearTime[node];
	// if(clearTime[node<<1]>invertTime[node<<1]&&clearTime[node<<1]>setTime[node<<1])
	// sTree[node << 1] = new pair(0,sTree[node<<1].min);
	// if(setTime[node<<1]>invertTime[node<<1]&&setTime[node<<1]>clearTime[node<<1])
	// sTree[node << 1] = new pair(1,sTree[node<<1].min);
	// else if(setTime[node<<1]>clearTime[node<<1])
	// sTree[node << 1] = new pair(0,sTree[node<<1].min);
	// else
	// if(clearTime[node<<1]==-1)
	// sTree[node << 1] = new pair(1-sTree[node<<1].av,sTree[node<<1].min);
	// else
	// sTree[node << 1] = new pair(1,sTree[node<<1].min);
	//
	// if(setTime[node<<1|1]>invertTime[node<<1|1]&&setTime[node<<1|1]>clearTime[node<<1|1])
	// sTree[node << 1|1] = new pair(1,sTree[node<<1|1].min);
	// else if(setTime[node<<1|1]>clearTime[node<<1|1])
	// sTree[node << 1|1] = new pair(0,sTree[node<<1|1].min);
	// else
	// if(clearTime[node<<1|1]==-1)
	// sTree[node << 1|1] = new pair(1-sTree[node<<1|1].av,sTree[node<<1|1].min);
	// else
	// sTree[node << 1|1] = new pair(1,sTree[node<<1|1].min);
	// invertTime[node] = -1;
	// setTime[node] = -1;
	// clearTime[node] =-1;
	//
	//
	// }
	//
	// long query(int i, int j) {
	// return query(1, 1, N, i, j);
	// }
	//
	// long query(int node, int b, int e, int i, int j) // O(log n)
	// {
	// if (i > e || j < b)
	// return 0;
	// return sTree[node].min;
	//// int mid = b + e >> 1;
	//// propagate(node, b, mid, e);
	//// int q1 = query(node << 1, b, mid, i, j);
	//// int q2 = query(node << 1 | 1, mid + 1, e, i, j);
	//// return q1 + q2;
	//
	// }
	//
	// }

	static class SegmentTree { // 1-based DS, OOP

		int N; // the number of elements in the array as a power of 2 (i.e. after padding)
		int[] array, sTree, lazy;

		SegmentTree(int N) {
//			array = in;
			this.N = N;
			sTree = new int[N << 1]; // no. of nodes = 2*N - 1, we add one to cross out index zero
			lazy = new int[N << 1];
			build(1, 1, N);
		}

		void build(int node, int b, int e) // O(n)
		{
			if (b == e)
				sTree[node] = 0;
			else {
				int mid = b + e >> 1;
				build(node << 1, b, mid);
				build(node << 1 | 1, mid + 1, e);
				sTree[node] = sTree[node << 1] + sTree[node << 1 | 1];
			}
		}


		void update_range(int i, int j, int type) // O(log n)
		{
			update_range(1, 1, N, i, j, type);
		}

//		void update_range(int node, int b, int e, int i, int j, int type) {
//			if (i > e || j < b)
//				return;
//			if (b >= i && e <= j) {
//				if (type == 1) {
//					sTree[node] = (e - b + 1);
//					lazy[node] = 1;
//				} else if (type == 2) {
//					lazy[node] = 2;
//					sTree[node] = 0;
//				} else {
//					lazy[node] = lazy[node] == 3 ? 0 : (lazy[node] == 1 ? 2 : lazy[node] == 2 ? 1 : 3);
//					sTree[node] = (sTree[node] == 0) ? (e - b + 1) : 0;
//				}
//			} else {
//				int mid = b + e >> 1;
//				propagate(node, b, mid, e);
//				update_range(node << 1, b, mid, i, j, type);
//				update_range(node << 1 | 1, mid + 1, e, i, j, type);
//				sTree[node] = sTree[node << 1] + sTree[node << 1 | 1];
//			}
//
//		}

		void update_range(int node, int b, int e, int i, int j, int val)
		{
			if(i > e || j < b)		
				return;
			if(b >= i && e <= j)		
			{
				if(val == 1){
					sTree[node] = (e-b+1);		
				}
				else if(val == 2){
					sTree[node] = 0;	
				}
				else{
					sTree[node] = (e-b+1) - sTree[node];		
				}	
				if(val == 3){
					lazy[node] = lazy[node] == 1?2:lazy[node] == 2?1:lazy[node] == 3?0:3;
				}
				else{
					lazy[node] = val;
				}	
			}							
			else		
			{
				int mid = ((b + e) >> 1);
				propagate(node, b, mid, e);
				update_range(node<<1,b,mid,i,j,val);
				update_range(node<<1|1,mid+1,e,i,j,val);
				sTree[node] = sTree[node<<1] + sTree[node<<1|1];
			}

		}void propagate2(int node, int b, int mid, int e)		
		{
			if(lazy[node] != 0){
				if(lazy[node] == 3){
					int org = lazy[node<<1];
					lazy[node<<1] = org == 1?2:org == 2?1:org == 3?0:3;
					org = lazy[node<<1|1];
					lazy[node<<1|1] = org == 1?2:org == 2?1:org == 3?0:3;
				}
				else{
					lazy[node<<1] = lazy[node];
					lazy[node<<1|1] = lazy[node];
				}
				if(lazy[node] == 1){
					sTree[node<<1] = (mid-b+1);		
					sTree[node<<1|1] = (e-mid);	
				}
				else if(lazy[node] == 2){
					sTree[node<<1] = 0;		
					sTree[node<<1|1] = 0;	
				}
				else{
					sTree[node<<1] = (mid-b+1) - sTree[node<<1];		
					sTree[node<<1|1] = (e-mid)- sTree[node<<1|1];	
				}
			}
			lazy[node] = 0;
		}
		void propagate(int node, int b, int mid, int e) {
			if (lazy[node] != 0) {
				if (lazy[node] == 3) {
					int org = lazy[node<<1];
					lazy[node<<1] = org == 1?2:org == 2?1:org == 3?0:3;
					org = lazy[node<<1|1];
					lazy[node<<1|1] = org == 1?2:org == 2?1:org == 3?0:3;
					sTree[node << 1] =  (mid - b + 1)-sTree[node << 1] ;
					sTree[node << 1 | 1] = (e - mid)-sTree[node << 1 | 1] ;
				} else {
					lazy[node << 1] = lazy[node];
					lazy[node << 1 | 1] = lazy[node];
				}
				if (lazy[node] == 2) {
					sTree[node << 1] = 0;
					sTree[node << 1 | 1] = 0;
				} else if (lazy[node] == 1) {
					sTree[node << 1] = (mid - b + 1);
					sTree[node << 1 | 1] = (e - mid);

				}
			}

			lazy[node] = 0;
		}

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

		int query(int node, int b, int e) // O(log n)
		{
			if(b==e)
				return b;
			int mid = (b + e) >> 1;
			propagate(node, b, mid, e);
			if(sTree[node<<1]<(mid-b+1))
				return query(node << 1, b, mid);
			else 
				return query(node << 1 | 1, mid + 1, e);
		}

	}

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

		public queries(int t, long l, long r) {
			type = t;
			this.l = l;
			this.r = r;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(in.readLine());
		TreeSet<Long> ts = new TreeSet<Long>();
		queries[] q = new queries[n];
		StringTokenizer st;
		ts.add(1l);
		for (int i = 0; i < q.length; i++) {
			st = new StringTokenizer(in.readLine());
			int t = Integer.parseInt(st.nextToken());
			long l = Long.parseLong(st.nextToken());
			long r = Long.parseLong(st.nextToken());
			q[i] = new queries(t, l, r);
			// System.out.println(t+" "+l+" "+r);
			ts.add(l);
			ts.add(r);
			ts.add(r + 1);
		}
		int idx = 1;
		TreeMap<Integer, Long> tm2 = new TreeMap<Integer, Long>();
		TreeMap<Long, Integer> tm = new TreeMap<Long, Integer>();
		for (Long cur : ts) {
			tm.put(cur, idx++);
//			System.out.println(cur + " " + (idx - 1));
			tm2.put(idx - 1, cur);
		}
		n = ts.size();
		int N = 1;
		while (N < n)
			N <<= 1; // padding
//		System.out.printl.,;n(N+" "+idx+" "+ts.size());
		SegmentTree sg = new SegmentTree(N);
		PrintWriter out = new PrintWriter(System.out);
		for (int i = 0; i < q.length; i++) {

			int type = q[i].type;
//			System.out.println(type);
			long r = q[i].r;
			long l = q[i].l;
//			System.out.println(tm.get(l) + " " + tm.get(r));
			sg.update_range(tm.get(l), tm.get(r), type);
			out.println(tm2.get(sg.query()));
		}
		out.flush();
		out.close();

	}
}