F2. Гелифиш и ликорис лучистый (сложная версия)
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии ограничения по времени и ограничения на $$$n$$$ и $$$q$$$ выше. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Гелифиш имеет массив, состоящий из $$$n$$$ множеств. Изначально все множества пусты.

Теперь Гелифиш выполнит $$$q$$$ операций. Каждая операция содержит одну операцию модификации и одну операцию запроса, для $$$i$$$-й ($$$1 \leq i \leq q$$$) операции:

Сначала идёт операция модификации, которая является одной из следующих:

  1. Операция вставки: Вам дано целое число $$$r$$$. Для множеств с $$$1$$$-го по $$$r$$$-й вставьте элемент $$$i$$$. Обратите внимание, что вставляемый элемент здесь — это $$$i$$$ — индекс операции, а не индекс множества.
  2. Операция разворота: Вам дано целое число $$$r$$$. Разверните префикс массива множеств с $$$1$$$-го по $$$r$$$-й элемент.
  3. Операция удаления: Вам дано целое число $$$x$$$. Удалите элемент $$$x$$$ из всех множеств, которые содержат $$$x$$$.

Затем следует операция запроса:

  • Операция запроса: Вам дано целое число $$$p$$$. Выведите наименьший элемент в $$$p$$$-м множестве (если $$$p$$$-е множество пусто, ответ считается равным $$$0$$$).

Теперь Флауэр должна ответить на все запросы. Пожалуйста, помогите ей!

Дополнительное ограничение: Гелифиш будет давать следующую операцию только после того, как Флауэр ответит на предыдущую операцию запроса. Другими словами, вам нужно решить эту задачу онлайн. Пожалуйста, обратитесь к формату ввода для получения дополнительных деталей.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n, q \leq 3 \cdot 10^5$$$) — количество множеств и количество операций.

Поскольку вам нужно отвечать на операции онлайн, операции будут закодированы.

$$$i$$$-я строка из следующих $$$q$$$ строк содержит три целых числа $$$a$$$, $$$b$$$ и $$$c$$$ ($$$1 \leq a \leq 3$$$, $$$1 \leq c \leq n$$$) — $$$i$$$-я операция в закодированной форме.

Здесь $$$a$$$ представляет тип операции модификации. Из них $$$a=1$$$ представляет Операцию вставки, $$$a=2$$$ представляет Операцию разворота, $$$a=3$$$ представляет Операцию удаления.

  • Если $$$a = 1$$$, то операция модификации — это Операция вставки. Будет гарантировано, что $$$1 \leq b \leq n$$$. $$$r$$$ будет вычисляться как $$$r=(b+\text{ans}_{i-1}-1) \bmod n + 1$$$.
  • Если $$$a=2$$$, то операция модификации — это Операция разворота. Будет гарантировано, что $$$1 \leq b \leq n$$$. $$$r$$$ будет вычисляться как $$$r=(b+\text{ans}_{i-1}-1) \bmod n + 1$$$.
  • Если $$$a=3$$$, то операция модификации — это Операция удаления. Будет гарантировано, что $$$1 \leq b \leq q$$$. $$$x$$$ будет вычисляться как $$$x=(b+\text{ans}_{i-1}-1) \bmod q + 1$$$.

Для операции запроса $$$p$$$ будет вычисляться как $$$p = (c+\text{ans}_{i-1}-1) \bmod n + 1$$$.

Здесь $$$ \text{ans}_{i} (1 \leq i \leq q)$$$ представляет ответ на операцию запроса в $$$i$$$-й операции. Кроме того, мы определяем $$$ \text{ans}_{0} = 0$$$.

Выходные данные

Для каждой операции запроса выведите ответ на запрос.

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

Все множества изначально пусты, поэтому массив равен $$$[\{\}, \{\}, \{\}, \{\}, \{\}]$$$.

С помощью метода декодирования, приведенного ранее, мы можем увидеть, что происходит в каждой операции:

  1. Для первой операции: $$$a = 1, r = 2, p = 2$$$. Операция модификации — это Операция вставки; элемент $$$1$$$ вставляется в первые два множества; поэтому массив становится $$$[\{1\}, \{1\}, \{\}, \{\}, \{\}]$$$, и наименьший элемент во втором множестве равен $$$1$$$.
  2. Для второй операции: $$$a = 2, r = 4, p = 2$$$. Операция модификации — это Операция разворота; первые четыре множества разворачиваются; поэтому массив становится $$$[\{\}, \{\}, \{1\}, \{1\}, \{\}]$$$, и второе множество пусто, что означает, что ответ равен $$$0$$$.
  3. Для третьей операции: $$$a = 1, r = 5, p = 3$$$. Операция модификации — это Операция вставки; элемент $$$3$$$ вставляется во все множества; поэтому массив становится $$$[\{3\}, \{3\}, \{1, 3\}, \{1, 3\}, \{3\}]$$$, и наименьший элемент в третьем множестве равен $$$1$$$.
  4. Для четвертой операции: $$$a = 2, r = 3, p = 1$$$. Операция модификации — это Операция разворота; первые три множества разворачиваются; поэтому массив становится $$$[\{1, 3\}, \{3\}, \{3\}, \{1, 3\}, \{3\}]$$$, и наименьший элемент в первом множестве равен $$$1$$$.
  5. Для пятой операции: $$$a = 1, r = 1, p = 3$$$. Операция модификации — это Операция вставки; элемент $$$5$$$ вставляется в первое множество; поэтому массив становится $$$[\{1, 3, 5\}, \{3\}, \{3\}, \{1, 3\}, \{3\}]$$$, и наименьший элемент в третьем множестве равен $$$3$$$.
  6. Для шестой операции: $$$a = 2, r = 2, p = 2$$$. Операция модификации — это Операция разворота; первые два множества разворачиваются; поэтому массив становится $$$[\{3\}, \{1, 3, 5\}, \{3\}, \{1, 3\}, \{3\}]$$$, и наименьший элемент во втором множестве равен $$$1$$$.
  7. Для седьмой операции: $$$a = 3, x = 3, p = 3$$$. Операция модификации — это Операция удаления; элемент $$$3$$$ удаляется из всех множеств; поэтому массив становится $$$[\{\}, \{1, 5\}, \{\}, \{1\}, \{\}]$$$, и третье множество пусто, что означает, что ответ равен $$$0$$$.
  8. Для восьмой операции: $$$a = 3, x = 1, p = 2$$$. Операция модификации — это Операция удаления; элемент $$$1$$$ удаляется из всех множеств; поэтому массив становится $$$[\{\}, \{5\}, \{\}, \{\}, \{\}]$$$, и наименьший элемент во втором множестве равен $$$5$$$.
  9. Для девятой операции: $$$a = 3, x = 5, p = 5$$$. Операция модификации — это Операция удаления; элемент $$$5$$$ удаляется из всех множеств; поэтому массив становится $$$[\{\}, \{\}, \{\}, \{\}, \{\}]$$$, и пятое множество пусто, что означает, что ответ равен $$$0$$$.
  10. Для десятой операции: $$$a = 3, x = 2, p = 4$$$. Операция модификации — это Операция удаления; элемент $$$2$$$ удаляется из всех множеств; поэтому массив становится $$$[\{\}, \{\}, \{\}, \{\}, \{\}]$$$, и четвертое множество пусто, что означает, что ответ равен $$$0$$$.

Обратите внимание, что хотя мы не вставляли элемент $$$2$$$ в множества, мы все равно удаляем элемент $$$2$$$ из всех множеств в десятой операции. Это означает, что операция Удаления не обязательно требует существования множества, содержащего удаляемый элемент. Это также показывает, что возможно иметь две операции Удаления, которые удаляют один и тот же элемент.