当前没有测试数据。

CF817F

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

样例输入 #1

3
1 3 4
3 1 6
2 1 3

样例输出 #1

1
3
1

样例 #2

样例输入 #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