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 A{

	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner();
		PrintWriter out=new PrintWriter(System.out);
		int n=sc.nextInt();
		int []t=new int [n];
		long []l=new long [n],r=new long [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);
		}
		long []a=new long [3*n+10];
		TreeMap<Long,Integer> map=new TreeMap();
		int id=1;
		for(long x:set) {
			map.put(x,id);
			a[id++]=x;
		}
		SegmentTree tree=new SegmentTree();
		for(int i=0;i<n;i++) {
			int k1=map.get(l[i]),k2=map.get(r[i]);
			tree.update(k1,k2,t[i]);
			out.println(a[tree.query()]);
		}
		out.close();

		
	}
	static class SegmentTree
	{
		int N;
		int []sum,lazy;
		SegmentTree(){
			N=(int)3e5+3;
			sum=new int [4*N];
			lazy=new int [4*N];
			
		}
		void update(int l,int r,int t) {
			update(1,1,N,l,r,t);
		}
		void update(int node,int tl,int tr,int l,int r,int t) {
			if(tr<l || r<tl)
				return;
			if(tl>=l && tr<=r) {
				if(t==1)
					sum[node]=tr-tl+1;
				else if(t==2)
					sum[node]=0;
				else sum[node]=tr-tl+1-sum[node];
				if(t==3)
					lazy[node]=lazy[node]==1?2:lazy[node]==2?1:3-lazy[node];
				else
					lazy[node]=t;
			}
			else {
				propagate(node, tl, tr);
				int mid=tl+tr>>1,left=node<<1,right=left+1;
				update(left,tl,mid,l,r,t);
				update(right,mid+1,tr,l,r,t);
				sum[node]=sum[left]+sum[right];
			}
		}
		void propagate(int node,int tl,int tr) {
			int left=node<<1,right=left+1;
			int mid=tl+tr>>1;
			if(lazy[node]>0) {
				int l=lazy[node];
				if(l==1) {
					sum[left]=mid-tl+1;
					sum[right]=tr-mid;
					lazy[left]=lazy[right]=l;
				}
				else if(l==2) {
					sum[left]=sum[right]=0;
					lazy[left]=lazy[right]=l;
				}
				else {
					sum[left]=mid-tl+1-sum[left];
					sum[right]=tr-mid-sum[right];
					lazy[left]=lazy[left]==1?2:lazy[left]==2?1:3-lazy[left];
					lazy[right]=lazy[right]==1?2:lazy[right]==2?1:3-lazy[right];
				}
				lazy[node]=0;
			}
			
			
		}
		
		int query() {
			return query(1,1,N);
		}
		int query(int node,int l,int r) {
			if(l==r)
				return l;
			int left=node<<1,right=left+1;
			int mid=l+r>>1;
			propagate(node, l, r);
			if(sum[left]==mid-l+1)
				return query(right,mid+1,r);
			else
				return query(left,l,mid);
		}
		
	}
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		Scanner(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		Scanner(String fileName) throws FileNotFoundException{
			br=new BufferedReader(new FileReader(fileName));
		}
		String next() throws IOException {
			while(st==null || !st.hasMoreTokens())
				st=new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		String nextLine() throws IOException {
			return br.readLine();
		}
		int nextInt() throws IOException{
			return Integer.parseInt(next());
		}
		long nextLong()  throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}
		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}
	}
}