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 \ge 1) integer number which is not presented in the set.
The first line contains one integer number n (1 \le n \le 105).
Next n lines contain three integer numbers t,l,r (1 \le t \le 3,1 \le l \le r \le 1018) - type of the query, left and right bounds.
Print MEX of the set after each query.
4 1 1 3 3 5 6 2 4 4 3 1 6\n · · \n · · \n · · \n · · \n
4 4 4 1\n \n \n \n
Here are contents of the set after each query in the first example:
{3,4} - the interval [3,4] is added {1,2,5,6} - numbers {3,4} from the interval [1,6] got deleted and all the others are added {5,6} - numbers {1,2} got deleted