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.HashMap;
import java.util.StringTokenizer;
import java.util.TreeSet;


public class F {



	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		int n = sc.nextInt();

		long[] idx = new long[4 * n + 5];

		HashMap<Long, Integer> map = new HashMap<>();
		

		long[] l = new long[n];
		long[] r = new long[n];
		int[] t = new int[n];

		TreeSet<Long> set = new TreeSet<>();
		set.add(1l);
		for (int i = 0; i < n; i++) {
			t[i] = sc.nextInt();
			l[i] = sc.nextLong();
			r[i] = sc.nextLong();
			
			set.add(l[i]);
			set.add(r[i]);
			set.add(r[i] + 1);
			set.add(l[i] + 1);


		}
		int c = 1;
		for(long x : set) {
			if(!map.containsKey(x)) {
				idx[c] = x;
				map.put(x, c++);
			}
		}

		int N = 1; while(N < set.size()) N <<= 1; //padding

		int[] in = new int[N + 1];
		SegmentTree st = new SegmentTree(in);

		for (int i = 0; i < n; i++) {
			st.update_range(map.get(l[i]), map.get(r[i]), t[i]);
			
			out.println(idx[st.query()]);
		}

		out.flush();
		out.close();
	}

	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[] in)		
		{
			array = in; N = in.length - 1;
			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] = array[b];
			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 val)		// O(log n) 
		{
			update_range(1,1,N,i,j,val);
		}

		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);			
					lazy[node] = val;	
				}

				if(val == 2) {
					sTree[node] = 0;			
					lazy[node] = val;	
				}

				if(val == 3) {
					sTree[node] = (e-b+1) - sTree[node];			
					switch (lazy[node]) {
					case 0:
						lazy[node] = 3;
						break;
					case 1:
						lazy[node] = 2;
						break;
					case 2:
						lazy[node] = 1;
						break;

					default:
						lazy[node] = 0;
						break;
					}	
				}

			}							
			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 propagate(int node, int b, int mid, int e)		
		{

			if(lazy[node] == 1) {
				lazy[node<<1] = 1;
				lazy[node<<1|1] = 1;
				sTree[node<<1] = (mid-b+1);	
				sTree[node<<1|1] = (e-mid);
			}

			if(lazy[node] == 2) {
				lazy[node<<1] = 2;
				lazy[node<<1|1] = 2;
				sTree[node<<1] = 0;	
				sTree[node<<1|1] = 0;
			}

			if(lazy[node] == 3) {
				switch (lazy[node<<1]) {
				case 0:
					lazy[node<<1] = 3;
					break;
				case 1:
					lazy[node<<1] = 2;
					break;
				case 2:
					lazy[node<<1] = 1;
					break;

				default:
					lazy[node<<1] = 0;
					break;
				}
				
				switch (lazy[node<<1|1]) {
				case 0:
					lazy[node<<1|1] = 3;
					break;
				case 1:
					lazy[node<<1|1] = 2;
					break;
				case 2:
					lazy[node<<1|1] = 1;
					break;

				default:
					lazy[node<<1|1] = 0;
					break;
				}
				sTree[node<<1] = (mid-b+1) - sTree[node<<1];	
				sTree[node<<1|1] = (e-mid) - sTree[node<<1|1];
			}

			lazy[node] = 0;
		}


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

		int query(int node, int b, int e)
		{	
			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 Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream System){br = new BufferedReader(new InputStreamReader(System));}
		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public String nextLine()throws IOException{return br.readLine();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		public double nextDouble() throws IOException {return Double.parseDouble(next());}
		public char nextChar()throws IOException{return next().charAt(0);}
		public Long nextLong()throws IOException{return Long.parseLong(next());}
		public boolean ready() throws IOException{return br.ready();}
		public void waitForInput(){for(long i = 0; i < 3e9; i++);}
	}



}