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

public class D {
	
	public static void main(String[] args) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		HashMap<Long, Integer> map1 = new HashMap<>();
		int MAX = 1 << 19;
		long[] map2 = new long[MAX];
		int n = sc.nextInt();
		map1.put(1L, 1); map2[1] = 1;
		SegmentTree st = new SegmentTree(new int[MAX + 1]);
		Triple[] a = new Triple[n];
		long[] arr = new long[3 * n];
		int idx = 0;
		for(int i = 0; i < n; i++)
		{
			int t = sc.nextInt();
			if(t == 2) t = 0;
			long l = sc.nextLong(), r = sc.nextLong();
			arr[idx++] = l;
			arr[idx++] = r + 1;
			arr[idx++] = r;
			a[i] = new Triple(t, l, r);
		}
		Arrays.sort(arr);
		int cur = 2;
		for(int i = 0; i < 3 * n; i++)
		{
			Integer mapped = map1.get(arr[i]);
			if(mapped == null) {mapped = cur; map1.put(arr[i], cur++);}
			map2[mapped] = arr[i];
		}
		for(int i = 0; i < n; i++)
		{
			st.update_range(map1.get(a[i].left), map1.get(a[i].right), a[i].type);
			int lo = 1, hi = MAX, ans = -1;
			while(lo <= hi)
			{
				int mid = (lo + hi) >> 1;
				int q = st.query(lo, mid);
				if(mid - lo + 1 == q)
					lo = mid + 1;
				else
					hi = (ans = mid) - 1;
			}
			out.println(map2[ans]);
		}
		out.flush();
		out.close();
	}
	
	static public class SegmentTree {
		
		int N; 
		int[] array, sTree, lazy;
		
		SegmentTree(int[] in)		
		{
			array = in; N = in.length - 1;
			sTree = new int[N<<1];	
			lazy = new int[N<<1];
			Arrays.fill(lazy, -1);
			build(1,1,N);
		}
		
		void build(int node, int b, int e)
		{
			if(b == e)					
				sTree[node] = array[b];
			else						
			{
				int mid = b + e >> 1;
				build(node<<1,b,mid);
				build(node<<1|1,mid+1,e);
				sTree[node] = sTree[node<<1]+sTree[node<<1|1];
			}
		}
		
		void update_range(int i, int j, int val) 
		{
			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 == 3)
				{
					sTree[node] = (e - b + 1) - sTree[node];
					if(lazy[node] == 0) lazy[node] = 1;
					else if(lazy[node] == 1) lazy[node] = 0;
					else if(lazy[node] == 3) lazy[node] = -1;
					else if(lazy[node] == -1) lazy[node] = 3;
				}
				else
				{
					sTree[node] = (e - b + 1) * val;			
					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] == 3)
			{
				sTree[node << 1] = (mid - b + 1) - sTree[node << 1];
				sTree[node << 1 | 1] = (e - mid) - sTree[node << 1 | 1];
				if(lazy[node << 1] == 0) lazy[node << 1] = 1;
				else if(lazy[node << 1] == 1) lazy[node << 1] = 0;
				else if(lazy[node << 1] == 3) lazy[node << 1] = -1;
				else if(lazy[node << 1] == -1) lazy[node << 1] = 3;
				
				if(lazy[node << 1|1] == 0) lazy[node << 1|1] = 1;
				else if(lazy[node << 1|1] == 1) lazy[node << 1|1] = 0;
				else if(lazy[node << 1|1] == 3) lazy[node << 1|1] = -1;
				else if(lazy[node << 1|1] == -1) lazy[node << 1|1] = 3;
			}
			else if(lazy[node] != -1)
			{
				sTree[node<<1] = (mid - b + 1) * lazy[node];		
				sTree[node<<1|1] = (e - mid) * lazy[node];		
				lazy[node<<1] = lazy[node];
				lazy[node<<1|1] = lazy[node];
			}
			lazy[node] = -1;
		}
		
		int query(int i, int j)
		{
			return query(1,1,N,i,j);
		}
		
		int query(int node, int b, int e, int i, int j)
		{
			if(i>e || j <b)
				return 0;		
			if(b>= i && e <= j)
				return sTree[node];
			int mid = b + e >> 1;
			propagate(node, b, mid, e);
			int q1 = query(node<<1,b,mid,i,j);
			int q2 = query(node<<1|1,mid+1,e,i,j);
			return q1 + q2;	
					
		}
	}

	static class Triple
	{
		int type;
		long left, right;
		Triple(int t, long l, long r)
		{
			type = t; left = l; right = r;
		}
	}
	
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {br = new BufferedReader(new InputStreamReader(system));}
		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public String nextLine()throws IOException{return br.readLine();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		public double nextDouble() throws IOException {return Double.parseDouble(next());}
		public char nextChar()throws IOException{return next().charAt(0);}
		public Long nextLong()throws IOException{return Long.parseLong(next());}
		public boolean ready() throws IOException{return br.ready();}
		public void waitForInput(){for(long i = 0; i < 3e9; i++);}
	}
}