← 返回题目列表

Codeforces · 817/F

F. MEX 查询

中文机器翻译题面 查看原题

给你一组整数,最初它是空的。您应该执行 n 个查询。

查询分为三种不同类型:

- 1 l r — 添加区间 [l, r] 中的所有缺失数字
- 2 l r — 从区间 [l, r] 中删除所有存在的数字
- 3 l r — 反转区间 [l, r] — 添加所有缺失的数字并从区间 [l, r] 中删除所有存在的数字

每次查询后,您应该输出集合的 MEX — 集合中未出现的最小正整数 (MEX ≥ 1)。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105)。

接下来的 n 行包含三个整数 t、l、r (1 ≤ t ≤ 3, 1 ≤ l ≤ r ≤ 1018) — 查询的类型、左边界和右边界。

输出

每次查询后打印该组的 MEX。

示例

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

注意

以下是第一个示例中每个查询后的集合内容:

1. {3, 4} — 添加区间 [3, 4]
2. {1, 2, 5, 6} — 区间 [1, 6] 中的数字 {3, 4} 被删除,所有其他的都被添加
3. {5, 6} — 号码 {1, 2} 已删除