Дано множество целых чисел, изначально пустое. Ваша задача — обработать n запросов.
Запросы бывают трех типов:
- 1 l r — Добавить все отсутствующие числа из интервала [l, r]
- 2 l r — Удалить все присутствующие числа из интервала [l, r]
- 3 l r — Инвертировать интервал [l, r] — добавить все отсутствующие и удалить все присутствующие числа из интервала [l, r]
После каждого запроса выведите MEX множества — наименьшее положительное (MEX ≥ 1) целое число, которого нет во множестве.
Выходные данные
Выведите MEX множества после каждого запроса.
Примечание
Рассмотрим содержимое множества после каждого из запросов первого примера:
- {3, 4} — интервал [3, 4] добавлен
- {1, 2, 5, 6} — числа {3, 4} из интервала [1, 6] удалены, а остальные добавлены
- {5, 6} — числа {1, 2} удалены
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 3 4
3 1 6
2 1 3
|
1
3
1
|
|
2
|
4
1 1 3
3 5 6
2 4 4
3 1 6
|
4
4
4
1
|