MEX Queries

题意翻译

- 维护一个集合，初始为空。 - 有 $3$ 种操作： 1. 把 $[l,r]$ 中在集合中没有出现过的数添加到集合中。 2. 把 $[l,r]$ 中在集合中出现过的数从集合中删掉。 3. 把 $[l,r]$ 中在集合中没有出现过的数添加到集合中，并把 $[l,r]$ 中在集合中出现过的数从集合中删掉。 - 每次操作后输出集合的 $\operatorname{MEX}$ —— 在集合中没有出现过的最小正整数。 - $1\le n\le 10^5$，$1\le l\le r\le 10^{18}$。

题目描述

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.

输入输出格式

输入格式

The first line contains one integer number $ n $ ( $ 1<=n<=10^{5} $ ). Next $ n $ lines contain three integer numbers $ t,l,r $ ( $ 1<=t<=3,1<=l<=r<=10^{18} $ ) — type of the query, left and right bounds.

输出格式

Print MEX of the set after each query.

输入输出样例

输入样例 #1

3
1 3 4
3 1 6
2 1 3

输出样例 #1

1
3
1

输入样例 #2

4
1 1 3
3 5 6
2 4 4
3 1 6

输出样例 #2

4
4
4
1

说明

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