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.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeSet;

/*
 public class _817F {

 }

 */

public class _817F
{
	class SegmentTree
	{
		class node
		{
			int penUp;
			int addCnt;
		}

		int n;
		node[] st;

		public SegmentTree(int n)
		{
			super();
			this.n = n;
			this.st = new node[4 * n];

			for (int i = 0; i < st.length; i++)
			{
				st[i] = new node();
			}
		}

		public int newT(int pt, int ct)
		{
			if (pt == 0)
			{
				return ct;
			}

			if (pt == 1)
			{
				if (ct == 1)
				{
					return 1;
				}
				else if (ct == 2)
				{
					return 2;
				}
				else
				{
					return 2;
				}
			}
			else if (pt == 2)
			{
				if (ct == 1)
				{
					return 1;
				}
				else if (ct == 2)
				{
					return 2;
				}
				else
				{
					return 1;
				}
			}
			else
			{
				if (ct == 1)
				{
					return 1;
				}
				else if (ct == 2)
				{
					return 2;
				}
				else
				{
					return 0;
				}
			}
		}

		int dfs(int i, int r1, int r2)
		{
			update(i, r1, r2);

			if (r1 == r2 && st[i].addCnt == 0)
			{
				return r1;
			}

			int mid = (r1 + r2) / 2;

			update(i * 2 + 1, r1, mid);
			if (st[i * 2 + 1].addCnt < mid - r1 + 1)
			{
				return dfs(i * 2 + 1, r1, mid);
			}
			else
			{
				return dfs(i * 2 + 2, mid + 1, r2);
			}
		}

		void update(int i, int r1, int r2)
		{
			if (st[i].penUp != 0)
			{
				if (st[i].penUp == 1)
				{
					st[i].addCnt = r2 - r1 + 1;
				}
				else if (st[i].penUp == 2)
				{
					st[i].addCnt = 0;
				}
				else
				{
					st[i].addCnt = r2 - r1 + 1 - st[i].addCnt;
				}

				if (r1 != r2)
				{
					st[i * 2 + 1].penUp = newT(st[i * 2 + 1].penUp, st[i].penUp);
					st[i * 2 + 2].penUp = newT(st[i * 2 + 2].penUp, st[i].penUp);
				}

				st[i].penUp = 0;
			}
		}

		public int updateLazy(int i, int r1, int r2, int ra, int rb, int t)
		{
			update(i, r1, r2);

			if (r2 < ra || r1 > rb)
			{
				return 0;
			}

			if (r1 >= ra && r2 <= rb)
			{
				int pv = st[i].addCnt;

				if (t == 1)
				{
					st[i].addCnt = (r2 - r1 + 1);
				}
				else if (t == 2)
				{
					st[i].addCnt = 0;
				}
				else
				{
					st[i].addCnt = r2 - r1 + 1 - st[i].addCnt;
				}

				if (r1 != r2)
				{
					st[i * 2 + 1].penUp = newT(st[i * 2 + 1].penUp, t);
					st[i * 2 + 2].penUp = newT(st[i * 2 + 2].penUp, t);
				}

				return st[i].addCnt - pv;
			}

			int mid = (r1 + r2) / 2;

			int p1 = updateLazy(i * 2 + 1, r1, mid, ra, rb, t);
			int p2 = updateLazy(i * 2 + 2, mid + 1, r2, ra, rb, t);

			st[i].addCnt = st[i].addCnt + p1 + p2;

			return p1 + p2;
		}
	}

	class query
	{
		int t;
		long l;
		long r;

		public query(int t, long l, long r)
		{
			super();
			this.t = t;
			this.l = l;
			this.r = r;
		}

	}

	public void solve() throws FileNotFoundException
	{
		InputStream inputStream = System.in;

		InputHelper inputHelper = new InputHelper(inputStream);

		PrintStream out = System.out;

		// actual solution
		int n = inputHelper.readInteger();

		Map<Long, Integer> cm = new HashMap<Long, Integer>();

		TreeSet<Long> lrl = new TreeSet<Long>();

		List<query> ql = new ArrayList<query>();

		for (int i = 0; i < n; i++)
		{
			int t = inputHelper.readInteger();
			long l = inputHelper.readLong();
			long r = inputHelper.readLong();

			query q = new query(t, l, r);

			lrl.add(l);
			lrl.add(r + 1);

			ql.add(q);
		}

		if (lrl.first() != 1)
		{
			for (int i = 0; i < n; i++)
			{
				System.out.println("1");
			}
			return;
		}

		int nn = lrl.size();
		long[] a = new long[nn];

		Iterator<Long> it = lrl.iterator();

		for (int i = 0; i < nn; i++)
		{
			long next = it.next();
			cm.put(next, i);
			a[i] = next;
		}

		// for (int i = 0; i < ql.size(); i++)
		// {
		// ql.get(i).l = cm.get(ql.get(i).l);
		// ql.get(i).r = cm.get(ql.get(i).r);
		// }

		SegmentTree segmentTree = new SegmentTree(nn);

		for (int i = 0; i < ql.size(); i++)
		{
			segmentTree.updateLazy(0, 0, nn - 1, cm.get(ql.get(i).l),
					cm.get(ql.get(i).r + 1) - 1, ql.get(i).t);

			System.out.println(a[segmentTree.dfs(0, 0, nn - 1)]);
		}
		// end here
	}

	public static void main(String[] args) throws FileNotFoundException
	{
		(new _817F()).solve();
	}

	class InputHelper
	{
		StringTokenizer tokenizer = null;
		private BufferedReader bufferedReader;

		public InputHelper(InputStream inputStream)
		{
			InputStreamReader inputStreamReader = new InputStreamReader(
					inputStream);
			bufferedReader = new BufferedReader(inputStreamReader, 16384);
		}

		public String read()
		{
			while (tokenizer == null || !tokenizer.hasMoreTokens())
			{
				try
				{
					String line = bufferedReader.readLine();
					if (line == null)
					{
						return null;
					}
					tokenizer = new StringTokenizer(line);
				}
				catch (IOException e)
				{
					e.printStackTrace();
				}
			}

			return tokenizer.nextToken();
		}

		public Integer readInteger()
		{
			return Integer.parseInt(read());
		}

		public Long readLong()
		{
			return Long.parseLong(read());
		}
	}
}