F. Запросы на MEX
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано множество целых чисел, изначально пустое. Ваша задача — обработать 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 множества после каждого запроса.

Примеры
Входные данные
3
1 3 4
3 1 6
2 1 3
Выходные данные
1
3
1
Входные данные
4
1 1 3
3 5 6
2 4 4
3 1 6
Выходные данные
4
4
4
1
Примечание

Рассмотрим содержимое множества после каждого из запросов первого примера:

  1. {3, 4} — интервал [3, 4] добавлен
  2. {1, 2, 5, 6} — числа {3, 4} из интервала [1, 6] удалены, а остальные добавлены
  3. {5, 6} — числа {1, 2} удалены