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.BigInteger;
 
/**
 *
 * @author usquare
 */

public class ProblemB {
    
    static long mod = (int) (1e9+7);
    static InputReader in;
    static PrintWriter out;
    
    static class SegmentTree {
        int st[];
        int lazy[];
        boolean flip[];
 
        SegmentTree(int n)  {
            st = new int[4*n];
            lazy = new int[4*n];
            flip = new boolean[4*n];
            Arrays.fill(lazy, -1);
        }
        
        int getMid(int s, int e) {
            return (s+e)>>1;
        }
        
        void lazyupdate(int ss,int ee,int si){
            if(lazy[si] != -1){
                if(ss != ee){
                    lazy[2*si] = lazy[si];
                    lazy[2*si+1] = lazy[si];
                    flip[2*si] = false;
                    flip[2*si+1] = false;
                }
                st[si] = (ee-ss+1) * lazy[si];
                lazy[si] = -1;
            }
            if(flip[si]){
                if(ss != ee){
                    flip[2*si] ^= true;
                    flip[2*si+1] ^= true;
                }
                st[si] = (ee-ss+1) - st[si];
                flip[si] = false;
            }
        }

        int merge(int a,int b){
            return a + b;
        }
        
        void update(int s, int e, int x, int y, int c, int si){
            if(s == x && e == y){
                lazy[si] = c;
                flip[si] = false;
            }
            else{
                lazyupdate(s, e, si);
                int mid = getMid(s, e);
                if(y <= mid)    
                    update(s, mid, x, y, c, 2*si);
                else if(x > mid)
                    update(mid + 1, e, x ,y ,c ,2*si + 1);
                else{
                    update(s, mid, x, mid, c, 2*si);
                    update(mid + 1, e, mid + 1, y, c, 2*si + 1);
                }
                lazyupdate(s, mid, 2*si);
                lazyupdate(mid + 1, e, 2*si + 1);
                st[si]=merge(st[2*si],st[2*si+1]);
            }
        }

        void update(int s, int e, int x, int y,int si){
            if(s == x && e == y){
                flip[si] ^= true;
            }
            else{
                lazyupdate(s, e, si);
                int mid = getMid(s, e);
                if(y <= mid)    
                    update(s, mid, x, y, 2*si);
                else if(x > mid)
                    update(mid + 1, e, x ,y ,2*si + 1);
                else{
                    update(s, mid, x, mid, 2*si);
                    update(mid + 1, e, mid + 1, y, 2*si + 1);
                }
                lazyupdate(s, mid, 2*si);
                lazyupdate(mid + 1, e, 2*si + 1);
                st[si]=merge(st[2*si],st[2*si+1]);
            }
        }
        
        int get(int s, int e, int si){

            lazyupdate(s, e, si);
            if(s == e){
                return s;
            }
            int mid = getMid(s, e);
            lazyupdate(s, mid, 2 * si);
            lazyupdate(mid + 1, e, 2 * si + 1);
            if(st[2 * si] < mid - s + 1)
                return get(s, mid, 2*si);
            else
                return get(mid + 1, e, 2*si + 1);
        }
    }
    
    static void solve() {
        
        in = new InputReader(System.in);
        out = new PrintWriter(System.out);  
        
        int n = in.nextInt();
        int[] t = new int[n];
        long[] l = new long[n];
        long[] r = new long[n];
        ArrayList<Long> list = new ArrayList<>();
        list.add(1l);
        for(int i = 0; i < n; i++){
            t[i] = in.nextInt();
            l[i] = in.nextLong();
            r[i] = in.nextLong();
            list.add(l[i]);
            list.add(r[i]);
            list.add(r[i] + 1);
        }
        Collections.sort(list);
        HashMap<Long,Integer> map = new HashMap<>();
        int j = 0;
        long[] arr = new long[4 * n];
        for(long k : list){
            if(map.containsKey(k)) continue;
            arr[j] = k;
            map.put(k, j++);
        }
        SegmentTree segmentTree = new SegmentTree(j);
        
        for(int i = 0; i < n; i++){
            if(t[i] == 1){
                segmentTree.update(0, j - 1, map.get(l[i]), map.get(r[i]), 1, 1);
            }
            else if(t[i] == 2){
                segmentTree.update(0, j - 1, map.get(l[i]), map.get(r[i]), 0, 1);
            }
            else{
                segmentTree.update(0, j - 1, map.get(l[i]), map.get(r[i]), 1);
            }
            out.println(arr[segmentTree.get(0, j - 1, 1)]);
        }
        
        out.close();
        
    }
    
    public static void main(String[] args) {
 
        new Thread(null,new Runnable() {
            @Override
            public void run() {
                try{
                    solve();
                }
                catch(Exception e){
                    e.printStackTrace();
                }
            }
        },"1",1<<26).start();
    }
    
    static class Pair implements Comparable<Pair>{
 
        int x,y;
        int i;
        
	Pair (int x,int y,int i){
		this.x = x;
		this.y = y;
		this.i = i;
	}
 
	Pair (int x,int y){
		this.x = x;
		this.y = y;
	}
        
	public int compareTo(Pair o) {
            if(this.x == o.x) Integer.compare(this.y, o.y);
            return Integer.compare(this.x,o.x);
		//return 0;
	}
 
            public boolean equals(Object o) {
            if (o instanceof Pair) {
                Pair p = (Pair)o;
                return p.x == x && p.y == y && p.i==i;
            }
            return false;
        }
 
        @Override
        public String toString() {
            return x+" "+y+" "+i;
        }
        
    } 
    
    static class Merge {
        
        public static void sort(long inputArr[]) {
            int length = inputArr.length;
            doMergeSort(inputArr,0, length - 1);
        }
        
        private static void doMergeSort(long[] arr,int lowerIndex, int higherIndex) {        
            if (lowerIndex < higherIndex) {
                int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
                doMergeSort(arr,lowerIndex, middle);
                doMergeSort(arr,middle + 1, higherIndex);
                mergeParts(arr,lowerIndex, middle, higherIndex);
            }
        }
        
        private static void mergeParts(long[]array,int lowerIndex, int middle, int higherIndex) {
            long[] temp=new long[higherIndex-lowerIndex+1];
            for (int i = lowerIndex; i <= higherIndex; i++) {
                temp[i-lowerIndex] = array[i];
            }
            int i = lowerIndex;
            int j = middle + 1;
            int k = lowerIndex;
            while (i <= middle && j <= higherIndex) {
                if (temp[i-lowerIndex] < temp[j-lowerIndex]) {
                    array[k] = temp[i-lowerIndex];
                    i++;
                } else {
                    array[k] = temp[j-lowerIndex];
                    j++;
                }
                k++;
            }
            while (i <= middle) {
                array[k] = temp[i-lowerIndex];
                k++;
                i++;
            }
            while(j<=higherIndex){
                array[k]=temp[j-lowerIndex];
                k++;
                j++;
            }
        }
 
    }
    
    static long add(long a,long b){
        long x=(a+b);
        while(x>=mod) x-=mod;
        return x;
    }
 
    static long sub(long a,long b){
        long x=(a-b);
        while(x<0) x+=mod;
        return x;
    }
    
    static long mul(long a,long b){
        a%=mod;
        b%=mod;
        long x=(a*b);
        return x%mod;
    }
 
    
    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;
    }
    static String rev(String s){
		StringBuilder sb=new StringBuilder(s);
		sb.reverse();
		return sb.toString();
    }
    
    static long gcd(long x,long y){
	if(y==0)
		return x;
	else
		return gcd(y,x%y);
    }
    
    static int gcd(int x,int y){
	if(y==0)
		return x;
	else 
		return gcd(y,x%y);
    }
    
    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;
    }
    
 
    static long mulmod(long  a,long b,long m) {
        if (m <= 1000000009) return a * b % m;
 
        long res = 0;
        while (a > 0) {
            if ((a&1)!=0) {
                res += b;
                if (res >= m) res -= m;
            }
            a >>= 1;
            b <<= 1;
            if (b >= m) b -= m;
        }
        return res;
    }
    
    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);
    }
    
    static int max(int a,int b){
	if(a>b)
		return a;
	else
		return b;
    }
 
    static int min(int a,int b){
	if(a>b)
		return b;
	else 
		return a;
    }
    
    static long max(long a,long b){
	if(a>b)
		return a;
	else
		return b;
    }
 
    static long min(long a,long b){
	if(a>b)
		return b;
	else 
		return a;
    }
 
    static long pow(long n,long p,long m){
	 long  result = 1;
	  if(p==0)
	    return 1;
          
	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;
    }
    
    static long pow(long n,long p){
	long  result = 1;
	  if(p==0)
	    return 1;
          
	while(p!=0)
	{
	    if(p%2==1)
	        result *= n;	    
	    p >>=1;
	    n*=n;	    
	}
	return result;
    }
    
    static void debug(Object... o) {
            System.out.println(Arrays.deepToString(o));
    }
     
    static class InputReader {
    
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;
 
        public InputReader(InputStream stream) {
                this.stream = stream;
        }
 
        public int snext() {
                if (snumChars == -1)
                        throw new InputMismatchException();
                if (curChar >= snumChars) {
                        curChar = 0;
                        try {
                                snumChars = stream.read(buf);
                        } catch (IOException e) {
                                throw new InputMismatchException();
                        }
                        if (snumChars <= 0)
                                return -1;
                }
                return buf[curChar++];
        }
 
        public int nextInt() {
                int c = snext();
                while (isSpaceChar(c)) {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-') {
                        sgn = -1;
                        c = snext();
                }
                int res = 0;
                do {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }
 
        public long nextLong() {
                int c = snext();
                while (isSpaceChar(c)) {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-') {
                        sgn = -1;
                        c = snext();
                }
                long res = 0;
                do {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }
 
        public int[] nextIntArray(int n) {
                int a[] = new int[n];
                for (int i = 0; i < n; i++) {
                        a[i] = nextInt();
                }
                return a;
        }
 
        public long[] nextLongArray(int n) {
                long a[] = new long[n];
                for (int i = 0; i < n; i++) {
                        a[i] = nextLong();
                }
                return a;
        }
 
        public String readString() {
                int c = snext();
                while (isSpaceChar(c)) {
                        c = snext();
                }
                StringBuilder res = new StringBuilder();
                do {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isSpaceChar(c));
                return res.toString();
        }
 
        public String nextLine() {
                int c = snext();
                while (isSpaceChar(c))
                        c = snext();
                StringBuilder res = new StringBuilder();
                do {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isEndOfLine(c));
                return res.toString();
        }
 
        public boolean isSpaceChar(int c) {
                if (filter != null)
                        return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        private boolean isEndOfLine(int c) {
                return c == '\n' || c == '\r' || c == -1;
        }
 
        public interface SpaceCharFilter {
                public boolean isSpaceChar(int ch);
        }
        
    }
}