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.util.*;
import java.io.*;
import java.math.*;
public class code5 {
	InputStream is;
	PrintWriter out;
	void solve()
	{
		int n=ni();
		Pair p[]=new Pair[n];
		ArrayList<Long> al=new ArrayList<Long>();
		for(int i=0;i<n;i++)
		{
			int type=ni();
			p[i]=new Pair(nl(),nl(),type);
			al.add(p[i].x);
			al.add(p[i].y);
			if(p[i].x!=1)
			al.add(p[i].x-1);
			if(p[i].y!=1)
				al.add(p[i].y-1);
			al.add(p[i].x+1);
			al.add(p[i].y+1);
		}
		al.add(1L);
		Collections.sort(al);
		HashMap<Long,Integer> hm=new HashMap<Long,Integer>();
		ArrayList<Long> hmrev=new ArrayList<Long>();
		hmrev.add(-1L);
		hm.put(al.get(0),1);
		hmrev.add(al.get(0));
		int count=1;
		for(int i=1;i<al.size();i++)
		{
			if((long)al.get(i)!=(long)al.get(i-1))
			{
				hm.put(al.get(i),++count);
				hmrev.add(al.get(i));
			}
		}
		segtree st=new segtree(count);
		for(int i=0;i<n;i++)
		{
			int l=hm.get(p[i].x);
			int r=hm.get(p[i].y);
			if(p[i].i==1)
			{
				st.update(l,r,1);
			}
			else if(p[i].i==2)
			{
				st.update(l,r,0);
			}
			else
			{
				st.update(l,r,2);
			}
			int low=1,high=count,ans=-1;
			while(low<=high)
			{
				int mid=(low+high)/2;
				//System.out.println(st.rangeq(1,mid)+" "+mid);
				if(st.rangeq(1,mid)<mid)
				{
					high=mid-1;
					ans=mid;
				}else{
					low=mid+1;
				}
			}
			//0System.out.println(ans);
			out.println(hmrev.get(ans));
		}
		
	}
	static class segtree{
		int arr[], st[], size,lazy[];
		segtree(int size)
		{
			this.size=size;
			st=new int[4*(size+1)+1];
			lazy=new int[4*(size+1)+1];
			Arrays.fill(lazy,-1);
		}
		int merge(int a,int b)
		{
			return a+b;
		}
		void update(int ul,int ur,int dx)
		{
			update(0,1,size,ul,ur,dx);
		}
		void update(int n,int l,int r,int ul,int ur,int dx)
		{
			if(lazy[n]==2)
			{
				st[n]=(r-l+1)-st[n];
				if(l!=r)
				{
						if(lazy[2*n+1]==0)
							lazy[2*n+1]=1;
						else if(lazy[2*n+1]==1)
							lazy[2*n+1]=0;
						else if(lazy[2*n+1]==-1)
							lazy[2*n+1]=2;
						else
							lazy[2*n+1]=-1;
						if(lazy[2*n+2]==0)
							lazy[2*n+2]=1;
						else if(lazy[2*n+2]==1)
							lazy[2*n+2]=0;
						else if(lazy[2*n+2]==-1)
							lazy[2*n+2]=2;
						else
							lazy[2*n+2]=-1;
				}
				lazy[n]=-1;
			}
			else if(lazy[n]!=-1){
				st[n]=(r-l+1)*lazy[n];
				if(l!=r)
				{
					lazy[2*n+1]=lazy[n];
					lazy[2*n+2]=lazy[n];
				}
				lazy[n]=-1;
			}
			if(ul>r||ur<l)
				return;
			if(ul<=l&&ur>=r)
			{
				if(dx==2)
					st[n]=(r-l+1)-st[n];
				else
					st[n]=(r-l+1)*dx;
				if(l!=r)
				{
					if(dx==2){
						if(lazy[2*n+1]==0)
							lazy[2*n+1]=1;
						else if(lazy[2*n+1]==1)
							lazy[2*n+1]=0;
						else if(lazy[2*n+1]==-1)
							lazy[2*n+1]=2;
						else
							lazy[2*n+1]=-1;
						if(lazy[2*n+2]==0)
							lazy[2*n+2]=1;
						else if(lazy[2*n+2]==1)
							lazy[2*n+2]=0;
						else if(lazy[2*n+2]==-1)
							lazy[2*n+2]=2;
						else
							lazy[2*n+2]=-1;
					}else
					{
						lazy[2*n+1]=dx;
						lazy[2*n+2]=dx;
					}
					
				}
				return;
			}
			int mid=(l+r)/2;
			update(2*n+1,l,mid,ul,ur,dx);
			update(2*n+2,mid+1,r,ul,ur,dx);
			st[n]=merge(st[2*n+1],st[2*n+2]);
		}
		
		int rangeq(int ql,int qr)
		{
			return rangeq(0,1,size,ql,qr);
		}
		int rangeq(int n,int l,int r,int ql,int qr)
		{
			if(lazy[n]==2)
			{
				st[n]=(r-l+1)-st[n];
				if(l!=r)
				{
					if(lazy[2*n+1]==0)
						lazy[2*n+1]=1;
					else if(lazy[2*n+1]==1)
						lazy[2*n+1]=0;
					else if(lazy[2*n+1]==-1)
						lazy[2*n+1]=2;
					else
						lazy[2*n+1]=-1;
					if(lazy[2*n+2]==0)
						lazy[2*n+2]=1;
					else if(lazy[2*n+2]==1)
						lazy[2*n+2]=0;
					else if(lazy[2*n+2]==-1)
						lazy[2*n+2]=2;
					else
						lazy[2*n+2]=-1;
				}
				lazy[n]=-1;
			}
			else if(lazy[n]!=-1){
				st[n]=(r-l+1)*lazy[n];
				if(l!=r)
				{
					lazy[2*n+1]=lazy[n];
					lazy[2*n+2]=lazy[n];
				}
				lazy[n]=-1;
			}
			if(ql>r||qr<l)
				return 0;
			if(ql<=l&&qr>=r)
				return st[n];
			int mid=(l+r)/2;
			return merge(rangeq(2*n+1,l,mid,ql,qr),rangeq(2*n+2,mid+1,r,ql,qr));
		}
	}
	public static int count(int x)
	{
		int num=0;
		while(x!=0)
		{
			x=x&(x-1);
			num++;
		}
		return num;
	}
	static long d, x, y;
	void extendedEuclid(long A, long B) {
	    if(B == 0) {
	        d = A;
	        x = 1;
	        y = 0;
	    }
	    else {
	        extendedEuclid(B, A%B);
	        long temp = x;
	        x = y;
	        y = temp - (A/B)*y;
	    }
	}
	long modInverse(long A,long M) //A and M are coprime
	{
	    extendedEuclid(A,M);
	    return (x%M+M)%M;    //x may be negative
	}
	public static void mergeSort(int[] arr, int l ,int r){
		if((r-l)>=1){
			int mid = (l+r)/2;
			mergeSort(arr,l,mid);
			mergeSort(arr,mid+1,r);
			merge(arr,l,r,mid);
		}
	}
	public static void merge(int arr[], int l, int r, int mid){
		int n1 = (mid-l+1), n2 = (r-mid);
		int left[] = new int[n1];
		int right[] = new int[n2];
		for(int i =0 ;i<n1;i++) left[i] = arr[l+i];
		for(int i =0 ;i<n2;i++) right[i] = arr[mid+1+i];
		int i =0, j =0, k = l;
		while(i<n1 && j<n2){
			if(left[i]>right[j]){
				arr[k++] = right[j++];
			}
			else{
				arr[k++] = left[i++];
			}
		}
		while(i<n1) arr[k++] = left[i++];
		while(j<n2) arr[k++] = right[j++];
	}
	public static void mergeSort(long[] arr, int l ,int r){
		if((r-l)>=1){
			int mid = (l+r)/2;
			mergeSort(arr,l,mid);
			mergeSort(arr,mid+1,r);
			merge(arr,l,r,mid);
		}
	}
	public static void merge(long arr[], int l, int r, int mid){
		int n1 = (mid-l+1), n2 = (r-mid);
		long left[] = new long[n1];
		long right[] = new long[n2];
		for(int i =0 ;i<n1;i++) left[i] = arr[l+i];
		for(int i =0 ;i<n2;i++) right[i] = arr[mid+1+i];
		int i =0, j =0, k = l;
		while(i<n1 && j<n2){
			if(left[i]>right[j]){
				arr[k++] = right[j++];
			}
			else{
				arr[k++] = left[i++];
			}
		}
		while(i<n1) arr[k++] = left[i++];
		while(j<n2) arr[k++] = right[j++];
	}
	 static class Pair implements Comparable<Pair>{
		 
	       long x,y,k,i;
	        
		Pair (long x,long y,int i){
			this.x=x;
			this.y=y;
			this.i=i;
		}
	        
		public int compareTo(Pair o) {
			if(this.x!=o.x)
				return Long.compare(x,o.x);
			else
				return Long.compare(y,o.y);
		}
	 
	        public boolean equals(Object o) {
	            if (o instanceof Pair) {
	                Pair p = (Pair)o;
	                return p.x == x && p.y == y && p.k==k;
	            }
	            return false;
	        }
	           
	 
	        @Override
	        public String toString() {
	            return  "("+x + " " + y +" "+k+" "+i+" )";
	        }
	    
	    } 
	    
	    public static boolean isPal(String s){
	        for(int i=0, j=s.length()-1;i<=j;i++,j--){
	                if(s.charAt(i)!=s.charAt(j)) return false;
	        }
	        return true;
	    }
	    public static String rev(String s){
			StringBuilder sb=new StringBuilder(s);
			sb.reverse();
			return sb.toString();
	    }
	    
	    public static long gcd(long x,long y){
		if(x%y==0)
			return y;
		else
			return gcd(y,x%y);
	    }
	    
	    public static int gcd(int x,int y){
	    	if(y==0) 
	    		return x; 
	    	return gcd(y,x%y);
	    }
	    
	    public static long gcdExtended(long a,long b,long[] x){
	        
	        if(a==0){
	            x[0]=0;
	            x[1]=1;
	            return b;
	        }
	        long[] y=new long[2];
	        long gcd=gcdExtended(b%a, a, y);
	        
	        x[0]=y[1]-(b/a)*y[0];
	        x[1]=y[0];
	        
	        return gcd;
	    }
	    
	    public static int abs(int a,int b){
		return (int)Math.abs(a-b);
	    }
	 
	    public static long abs(long a,long b){
		return (long)Math.abs(a-b);
	    }
	    
	    public static int max(int a,int b){
		if(a>b)
			return a;
		else
			return b;
	    }
	 
	    public static int min(int a,int b){
		if(a>b)
			return b;
		else 
			return a;
	    }
	    
	    public static long max(long a,long b){
		if(a>b)
			return a;
		else
			return b;
	    }
	 
	    public static long min(long a,long b){
		if(a>b)
			return b;
		else 
			return a;
	    }
	 
	    public static long pow(long n,long p,long m){
		 long  result = 1;
		  if(p==0)
		    return 1;
		if (p==1)
		    return n;
		while(p!=0)
		{
		    if(p%2==1)
		        result *= n;
		    if(result>=m)
		    result%=m;
		    p >>=1;
		    n*=n;
		    if(n>=m)
		    n%=m;
		}
		return result;
	    }
	    
	    public static long pow(long n,long p){
		long  result = 1;
		  if(p==0)
		    return 1;
		if (p==1)
		    return n;
		while(p!=0)
		{
		    if(p%2==1)
		        result *= n;	    
		    p >>=1;
		    n*=n;	    
		}
		return result;
	    }
	    public static void debug(Object... o) {
			System.out.println(Arrays.deepToString(o));
		}
	    void run() throws Exception {
			is = System.in;
			out = new PrintWriter(System.out);
			solve();
			out.flush();
		}
	   
	    public static void main(String[] args) throws Exception {
			new Thread(null, new Runnable() {
				public void run() {
					try {
						new code5().run();
					} catch (Exception e) {
						e.printStackTrace();
					}
				}
			}, "1", 1 << 26).start();

		}
	    private byte[] inbuf = new byte[1024];
		public int lenbuf = 0, ptrbuf = 0;
	 
		private int readByte() {
			if (lenbuf == -1)
				throw new InputMismatchException();
			if (ptrbuf >= lenbuf) {
				ptrbuf = 0;
				try {
					lenbuf = is.read(inbuf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return -1;
			}
			return inbuf[ptrbuf++];
		}
	 
		private boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}
	 
		private int skip() {
			int b;
			while ((b = readByte()) != -1 && isSpaceChar(b));
			return b;
		}
	 
		private double nd() {
			return Double.parseDouble(ns());
		}
	 
		private char nc() {
			return (char) skip();
		}
	 
		private String ns() {
			int b = skip();
			StringBuilder sb = new StringBuilder();
			while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}
	 
		private char[] ns(int n) {
			char[] buf = new char[n];
			int b = skip(), p = 0;
			while (p < n && !(isSpaceChar(b))) {
				buf[p++] = (char) b;
				b = readByte();
			}
			return n == p ? buf : Arrays.copyOf(buf, p);
		}
	 
		private char[][] nm(int n, int m) {
			char[][] map = new char[n][];
			for (int i = 0; i < n; i++)
				map[i] = ns(m);
			return map;
		}
	 
		private int[] na(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = ni();
			return a;
		}
		private long[] nl(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nl();
			return a;
		}
	 
		private int ni() {
			int num = 0, b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
	 
			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}
	 
		private long nl() {
			long num = 0;
			int b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}
	 
			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}
	 
}