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.*;

public class Main3 {
	static long oo = (long)1e18|1;
	public static void main(String[] args) throws Throwable 
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		TreeSet<Long> set = new TreeSet<Long>();
		set.add(1l);
		set.add(oo);
		long [][] query = new long[n][3];
		for (int zz = 0; zz < n; zz++) 
		{
			long  t = sc.nextLong() , l = sc.nextLong(), r = sc.nextLong();
			query[zz][0] = t;
			query[zz][1] = l;
			query[zz][2] = r;
			set.add(l);
			set.add(r);
			set.add(l-1);
			set.add(r+1);
		}
		if(set.contains(0l))set.remove(0l);
		long[] list = new long[set.size()];
		HashMap<Long, Integer> valToidx = new HashMap<Long, Integer>();
		HashMap<Integer, Long> idxToVal = new HashMap<Integer, Long>();
		int idx = 0;
		for(long i : set)
			list[idx++] = i;
		idx = 1;
		for(long i : set)
		{
			valToidx.put(i, idx);
			idxToVal.put(idx++, i);
		}
		SegmentTree tree = new SegmentTree(set.size());
		
		for (int i = 0; i < query.length; i++) {
			tree.update(valToidx.get(query[i][1]), valToidx.get(query[i][2]), (int) query[i][0]);
			sb.append(idxToVal.get(tree.query())+"\n");
		}
		System.out.print(sb);
	}
	
	static class SegmentTree
	{
		long arr[];
		int n;
		int[] lazy;
		
		public SegmentTree(int N)
		{
			n = N;
			arr = new long[n<<2];
			lazy = new int[arr.length];
		}
		
		int left(int cur){return cur<<1;}
		int right(int cur){return cur<<1|1;}
		

		void update(long lq,long rq,int v)
		{
			update(1, 1, n, lq, rq, v);
		}
		
		void update(int cur,int l,int r,long lq,long rq,int v)
		{
			propagate(cur, l, r);
			if(l>rq || r<lq)return;
			if(l>=lq && r<=rq)
			{
				lazy[cur] = v;
				propagate(cur, l, r);
			}
			else
			{
				int mid = (l+r)>>1;
				update(left(cur), l, mid, lq, rq, v);
				update(right(cur), mid+1, r, lq, rq, v);
				arr[cur] = arr[left(cur)] + arr[right(cur)];
			}
		}
		
		void propagate(int cur,int l,int r)
		{
			if(lazy[cur]==0)return;
			if(lazy[cur]==1) // Set
				arr[cur] = r - l + 1;
			else if(lazy[cur]==2) // Reset
				arr[cur] = 0;
			else if(lazy[cur]==3) // Invert
			{
				if(arr[cur]==0)arr[cur] = r - l + 1;
				else arr[cur] = r - l + 1 - arr[cur];
			}
			if(l!=r)
				if(lazy[cur]!=3)
					lazy[left(cur)] = lazy[right(cur)] = lazy[cur];
				else
				{
					lazy[left(cur)] = 3 - lazy[left(cur)];
					lazy[right(cur)] = 3 - lazy[right(cur)];
				}
			lazy[cur] = 0;
		}

		int query()
		{
			return query(1, 1, n);
		}
		
		int query(int cur,int l,int r)
		{
			propagate(cur, l, r);
			if(arr[cur] == r-l+1)return n;
			if(arr[cur] == 0)
				return l;
			else
			{
				int mid = (l+r)>>1;
				propagate(left(cur), l, mid);
				propagate(right(cur), mid+1, r);
				if(arr[left(cur)]!=mid-l+1)return query(left(cur), l, mid);
				return query(right(cur), mid+1, r);
			}
		}
	}
	
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;
		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}		
		public long nextLong() throws NumberFormatException, IOException {return Long.parseLong(next());}
		public Scanner(FileReader r){	br = new BufferedReader(r);}
		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 String nextLine() throws IOException {return br.readLine();}
		public boolean ready() throws IOException {return br.ready();}
	}

	
}