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.*;
import java.util.*;

public class Main{
	static public 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[] sTree, lazy;
		int[] array;
		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];
			Arrays.fill(lazy, -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==2) {//flip
					sTree[node]=(e-b+1)-sTree[node];
					if(lazy[node]==-1) {
						lazy[node]=2;
					}
					else {
						if(lazy[node]==2) {
							lazy[node]=-1;
						}
						else //0 means unset then flip -> set || 1 means set then flip -> unset
							lazy[node]^=1;
					}
				}
				else {
					sTree[node] = val*(e-b+1);			
					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 propagate(int node, int b, int mid, int e)		
		{
			if(lazy[node]==-1)return;
			
			if(lazy[node]==2) {
				if(lazy[node<<1]==-1) {
					lazy[node<<1] = lazy[node];				
				}
				else {
					if(lazy[node<<1]==2) {
						lazy[node<<1]=-1;
					}
					else
						lazy[node<<1]^=1;
				}
				if(lazy[node<<1|1]==-1) {
					lazy[node<<1|1] = lazy[node];				
				}
				else {
					if(lazy[node<<1|1]==2) {
						lazy[node<<1|1]=-1;
					}
					else
						lazy[node<<1|1]^=1;
				}
			}
			else {
				lazy[node<<1] = lazy[node];	
				lazy[node<<1|1] = lazy[node];
			}
			
			if(lazy[node]==2) {//flip
				sTree[node<<1]=(mid-b+1)-sTree[node<<1];
				sTree[node<<1|1]=(e-mid)-sTree[node<<1|1];
			}
			else {
				sTree[node<<1] = lazy[node]*(mid-b+1);		
				sTree[node<<1|1] = lazy[node]*(e-mid);	
			}
			lazy[node] = -1;
		}
		
		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);
			
			int left=node<<1,right=node<<1|1;
			int lenLeft=(mid-b+1);
			
			if(sTree[left]==lenLeft) {
				return query(right, mid+1, e);
			}
			return query(left,b,mid);
			
					
		}
	}
   	static void main() throws Exception{
   		int n=sc.nextInt();
   		long[][]q=new long[n][2];
   		
   		HashSet<Long>all=new HashSet<>();
   		all.add(1l);
   		for(int i=0;i<n;i++) {
   			int cmd=sc.nextInt();
   			long left=sc.nextLong();
   			long right=sc.nextLong();
   			q[i]=new long[] {cmd,left,right};
   			all.add(left);
   			all.add(right);
   			all.add(right+1);
   		}
   		long[]nums=new long[all.size()];
   		int c=0;
   		for(long i:all) {
   			nums[c++]=i;
   		}
   		HashMap<Long, Integer>map=new HashMap<>();
   		shuffle(nums);
   		Arrays.sort(nums);
   		for(int i=0;i<nums.length;i++) {
   			map.put(nums[i], i+1);
   		}
//   		System.out.println(Arrays.toString(nums));
   		int N = 1; while(N < all.size()) N <<= 1; //padding
   		SegmentTree st=new SegmentTree(new int[N+1]);
   		for(long[]query:q) {
   			int left=map.get(query[1]),right=map.get(query[2]);
   			int val=0;
   			if(query[0]==1) {
   				val=1;
   			}
   			else {
   				if(query[0]==3) {
   					val=2;
   				}
   			}
//   			System.out.println(val+" "+left+" "+right);
   			st.update_range(left, right, val);
   			int idx=st.query()-1;
   			pw.println(nums[idx]);
   		}
	}
	public static void main(String[] args) throws Exception{
		pw=new PrintWriter(System.out);
		sc = new MScanner(System.in);
		int tc=1;
		while(tc-->0)main();
		pw.flush();
	}
	static PrintWriter pw;
	static MScanner  sc;
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] intArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] longArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public int[] intSortedArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public long[] longSortedArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public Integer[] IntegerArr(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] LongArr(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		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() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
	static void shuffle(int[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			int tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
	static void shuffle(long[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			long tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
}