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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class A {

	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		TreeSet<Interval> set = new TreeSet<>();  // set of disjoint intervals
		int n = sc.nextInt();
		while(n-->0)
		{
			int t = sc.nextInt();
			long l = sc.nextLong(), r = sc.nextLong();
			
			Interval cur = new Interval(l, r);
			Interval test = new Interval(r, -1);

			if(t == 1)
				addInterval(set, cur);
			else
			{
				ArrayList<Interval> newIntervals = new ArrayList<>();
				long rightEnd = cur.right;
				boolean prefixInterval = true;
				while(true)
				{
					Interval prev = set.floor(test);
					if(prev == null || prev.right < cur.left)
						break;
					set.remove(prev);
					if(prev.left < cur.left)
						set.add(new Interval(prev.left, cur.left - 1));
					if(prev.right > cur.right)
						set.add(new Interval(cur.right + 1, prev.right));
					
					if(t == 3 && prev.right < rightEnd)
						newIntervals.add(new Interval(prev.right + 1, rightEnd));
					
					rightEnd = prev.left - 1;
					if(t == 3 && prev.left <= cur.left)
						prefixInterval = false;
				}
				if(t == 3 && prefixInterval)
					newIntervals.add(new Interval(cur.left, rightEnd));
				for(Interval i: newIntervals)
					addInterval(set, i);
			}

			
			if(set.isEmpty())
				out.println(1);
			else
			{
				Interval x = set.first();
				if(x.left > 1)
					out.println(1);
				else
					out.println(x.right + 1);
			}
		}
		out.close();
	}
	
	static void addInterval(TreeSet<Interval> set, Interval cur)
	{
		Interval test = new Interval(cur.right, -1);
		while(true)
		{
			Interval prev = set.floor(test);
			if(prev == null || prev.right + 1 < cur.left)
				break;
			set.remove(prev);
			cur = cur.merge(prev);
			test.left = cur.right;
		}
		Interval nxt = set.ceiling(test);
		if(nxt != null && nxt.left == cur.right + 1)
		{
			set.remove(nxt);
			cur = cur.merge(nxt);
		}
		set.add(cur);
	}
	
	static class Interval implements Comparable<Interval>
	{
		long left, right;
		
		Interval(long a, long b) { left = a; right = b; }
		
		Interval merge(Interval x)
		{
			long ll = Math.min(x.left, left);
			long rr = Math.max(x.right, right);
			return new Interval(ll, rr);
		}
		@Override
		public int compareTo(Interval o) { return left == o.left ? 0 : left > o.left ? 1 : -1; }
		
	}
	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

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

		public Scanner(String s) throws FileNotFoundException{	br = new BufferedReader(new FileReader(s));}

		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 double nextDouble() throws IOException { return Double.parseDouble(next()); }

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