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:
/* Author: Ronak Agarwal */
import java.io.* ; import java.util.* ; import java.math.* ;
import static java.lang.Math.min ;
import static java.lang.Math.max ;
import static java.lang.Math.abs ;
/* Thread is created here to increase the stack size of the java code so that recursive dfs can be performed */
public class Codeshefcode{
	public static void main(String[] args) throws IOException{
		new Thread(null,new Runnable(){	public void run(){ exec_Code() ;} },"Solver",1l<<27).start() ;
	}
	static void exec_Code(){
		try{
			Solver Machine = new Solver() ;
			Machine.Solve() ; Machine.Finish() ;}
		catch(Exception e){ e.printStackTrace() ; print_and_exit() ;}
		catch(Error e){ e.printStackTrace() ; print_and_exit() ; }
	}
	static void print_and_exit(){ System.out.flush() ; System.exit(-1) ;}
}
/* Implementation of the pair class, useful for every other problem */
class pair implements Comparable<pair>{
	long x ; long y ;
	pair(long _x,long _y){ x=_x ; y=_y ;} 
	public int compareTo(pair p){
		return (this.x<p.x ? -1 : (this.x>p.x ? 1 : (this.y<p.y ? -1 : (this.y>p.y ? 1 : 0)))) ;
	}
}
/* Main code starts here */
class Solver extends Template{
	int seg[],laz[],lazi[] ;
	public void Solve() throws IOException{
		int q = ip.i() ;
		int type[] = new int[q] ;
		pair qry[] = new pair[q] ;
		for(int i=0 ; i<q ; i++){
			type[i] = ip.i() ;
			qry[i] = new pair(ip.l(),ip.l()) ;
		}
		myset pts = new myset() ;
		for(pair p : qry){
			pts.add(p.x) ;
			pts.add(p.y) ;
		}
		mylist ls = new mylist() ;
		long prev=0 ;
		for(long elem : pts){
			if(elem>(prev+1))
				ls.add(prev+1) ;
			prev = elem ;
		}
		ls.add(pts.last()+1) ;
		pts.addAll(ls) ;
		int n = pts.size() ;
		mymap mp = new mymap() ;
		long mP[] = new long[n+1] ;
		seg = new int[5*n] ;
		laz = new int[5*n] ;
		lazi = new int[5*n] ;
		int ptr=1 ;
		for(long elem : pts){
			mP[ptr] = elem ;
			mp.put(elem,ptr++) ;
		}
		for(int i=0 ; i<q ; i++)
			qry[i] = new pair(mp.get(qry[i].x),mp.get(qry[i].y)) ;
		for(int i=0 ; i<q ; i++){
			update(1,1,n,(int) qry[i].x,(int) qry[i].y,type[i]) ;
			int l=1 ; int r=n ;
			int nd=1 ;
			rLazy(nd,l,r) ;
			nd*=2 ;
			while(l!=r){
				int m = (l+r)/2 ;
				int sum = get(nd,l,m) ;
				// if(i==1)
				// 	pln(l+" "+m+" "+r+" "+sum+" "+nd) ;
				if(sum==(m-l+1)){
					l=m+1 ;
					nd++ ;
					rLazy(nd,l,r) ;
				}else
					r=m ;
				nd*=2 ;
			}
			pln(mP[r]) ;
		}

	}
	void rLazy(int i,int s,int e){
		if(laz[i]!=0 || lazi[i]!=0){
			if(laz[i]!=0)
				seg[i] = laz[i]==1 ? (e-s+1) : 0 ;
			else
				seg[i] = lazi[i]==1 ? ((e-s+1)-seg[i]) : seg[i] ;
			if(s!=e){
				addLaz(i,2*i) ;
				addLaz(i,2*i+1) ;
			}
			laz[i]=0 ; lazi[i]=0 ;
		}
	}
	void addLaz(int i,int j){
		if(laz[i]!=0){
			laz[j]=laz[i] ; 
			lazi[j]=0 ;
		}else if(lazi[i]!=0){
			if(laz[j]!=0)
				laz[j] = -laz[j] ;
			else
				lazi[j] = 1-lazi[j] ;
		}
	}
	void update(int i,int s,int e,int l,int r,int typ){
		rLazy(i,s,e) ;
		if(r<s || e<l) return ;
		if(l<=s && e<=r){
			if(typ==1){laz[i]=1 ; lazi[i]=0 ;}
			else if(typ==2){laz[i]=-1 ; lazi[i]=0 ;}
			else{laz[i]=0 ; lazi[i]=1 ;}
			rLazy(i,s,e) ;
			return ;
		}
		int m = (s+e)/2 ;
		update(2*i,s,m,l,r,typ) ; update(2*i+1,m+1,e,l,r,typ) ;
		seg[i] = seg[2*i]+seg[2*i+1] ;
	}
	int get(int i,int s,int e){
		rLazy(i,s,e) ;
		return seg[i] ;
	}

}

/* All the useful functions,constants,renamings are here*/
class Template{
	/* Constants Section */
	final int INT_MIN = Integer.MIN_VALUE ; final int INT_MAX = Integer.MAX_VALUE ;
	final long LONG_MIN = Long.MIN_VALUE ; final long LONG_MAX = Long.MAX_VALUE ;
	static long MOD = 1000000007 ;
	static Reader ip = new Reader(System.in) ;	
	static PrintWriter op = new PrintWriter(System.out) ;
	/* Methods for writing */
	static void p(Object o){ op.print(o) ; }
	static void pln(Object o){ op.println(o) ;}
	static void Finish(){ op.flush();	op.close(); }
	/* Implementation of operations modulo MOD */
	static long inv(long a){ return powM(a,MOD-2) ; }
	static long m(long a,long b){ return (a*b)%MOD ; }
	static long d(long a,long b){ return (a*inv(b))%MOD ; }
	static long powM(long a,long b){
		if(b<0) return powM(inv(a),-b) ;
		long val=a ; long ans=1 ;
		while(b!=0){
			if((b&1)==1) ans = (ans*val)%MOD ; 
			val = (val*val)%MOD ; 
			b/=2 ;
		}
		return ans ;
	}
	/* Renaming of some generic utility classes */
	final static class mylist extends ArrayList<Long>{}
	final static class myset extends TreeSet<Long>{}
	final static class mystack extends Stack<Integer>{}
	final static class mymap extends TreeMap<Long,Integer>{}
}

class Reader{
	BufferedReader reader;
	StringTokenizer tkz;
	Reader(InputStream input) {
		reader = new BufferedReader(new InputStreamReader(input)) ;
		tkz = new StringTokenizer("") ;
	}
	String s() throws IOException{
		while (!tkz.hasMoreTokens()) tkz = new StringTokenizer(reader.readLine()) ;
		return tkz.nextToken() ;
	}
	int i() throws IOException{ return Integer.parseInt(s()) ;}
	long l() throws IOException{ return Long.parseLong(s()) ;}
	double d() throws IOException{	return Double.parseDouble(s()) ;}
}