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.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class A {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt();
		int [] t = new int[n];
		long [] l = new long[n];
		long [] r = new long[n];
		TreeMap<Long, Integer> set = new TreeMap<>();
		set.put(1L, 0);
		for (int i = 0; i < r.length; i++) {
			t[i] = sc.nextInt();
			l[i] = sc.nextLong();
			r[i] = sc.nextLong();
			set.put(l[i], 0);
			set.put(r[i], 0);
			set.put(r[i]+1, 0);
		}
		long [] un = new long[set.size()+1];
		int idx = 1;
		for(long i:set.keySet()){
			un[idx] = i;
			set.put(i, idx++);
		}
		int N = 1; while(N < idx) N <<= 1; //padding
		SegmentTree sg = new SegmentTree(N);
		for (int i = 0; i < r.length; i++) {
			sg.update_range(set.get(l[i]), set.get(r[i]), t[i]);
			out.println(un[sg.query()]);
		}
		out.flush();
		out.close();
	}

	static 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;

		SegmentTree(int n)		
		{
			N = n;
			sTree = new int[N<<1];		//no. of nodes = 2*N - 1, we add one to cross out index zero
			lazy = new int[N<<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 == 1){
					sTree[node] = (e-b+1);		
				}
				else if(val == 2){
					sTree[node] = 0;	
				}
				else{
					sTree[node] = (e-b+1) - sTree[node];		
				}	
				if(val == 3){
					lazy[node] = lazy[node] == 1?2:lazy[node] == 2?1:lazy[node] == 3?0:3;
				}
				else{
					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] != 0){
				if(lazy[node] == 3){
					int org = lazy[node<<1];
					lazy[node<<1] = org == 1?2:org == 2?1:org == 3?0:3;
					org = lazy[node<<1|1];
					lazy[node<<1|1] = org == 1?2:org == 2?1:org == 3?0:3;
				}
				else{
					lazy[node<<1] = lazy[node];
					lazy[node<<1|1] = lazy[node];
				}
				if(lazy[node] == 1){
					sTree[node<<1] = (mid-b+1);		
					sTree[node<<1|1] = (e-mid);	
				}
				else if(lazy[node] == 2){
					sTree[node<<1] = 0;		
					sTree[node<<1|1] = 0;	
				}
				else{
					sTree[node<<1] = (mid-b+1) - sTree[node<<1];		
					sTree[node<<1|1] = (e-mid)- sTree[node<<1|1];	
				}
			}
			lazy[node] = 0;
		}

		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);
			if(sTree[node<<1] < mid-b+1)
				return query(node<<1,b,mid);
			else
				return query(node<<1|1,mid+1,e);
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(FileReader fileReader) {
			br = new BufferedReader(fileReader);
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public boolean ready() throws IOException {
			return br.ready();
		}
	}
}