给你一组整数,最初它是空的。您应该执行 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} 已删除