A. Дикое дерево
ограничение по времени на тест
9 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Изначально вам дано дерево, состоящее из одной корневой вершины с номером $$$1$$$. В этой вершине записано целое число $$$a_1$$$.

Вам предстоит обрабатывать поступающие запросы, которые могут быть одного из трех типов. Обратите внимание, что задача решается в онлайн-режиме. Параметры запросов, которые вам даются во входных данных, зашифрованы.

Пусть $$$last$$$ — ответ на последний запрос 3-го типа. Изначально $$$last = 0$$$. Если в ответ на запрос 3-го типа не было найдено подходящего числа (выведено -1), то значение $$$last$$$ становится равным $$$0$$$.

Для декодирования параметров очередного запроса используются следующие формулы, где $$$V$$$ — текущее количество вершин в дереве до выполнения запроса:

  1. 1 $$$p'$$$ $$$a'$$$ — добавить новую вершину в качестве ребенка существующей вершины.
    • $$$p = ((p' \oplus last) \bmod V) + 1$$$
    • $$$a = ((a' \oplus last) \bmod 10^9) + 1$$$
    Новой вершине автоматически присваивается минимальный свободный натуральный номер $$$V + 1$$$. В ней будет записано число $$$a$$$.
  2. 2 $$$v'$$$ $$$a'$$$ — изменить число, записанное в вершине.
    • $$$v = ((v' \oplus last) \bmod V) + 1$$$
    • $$$a = ((a' \oplus last) \bmod 10^9) + 1$$$
    Значение в вершине $$$v$$$ меняется на $$$a$$$.
  3. 3 $$$u'$$$ $$$v'$$$ $$$x'$$$ — найти минимальное число на пути.
    • $$$u = ((u' \oplus last) \bmod V) + 1$$$
    • $$$v = ((v' \oplus last) \bmod V) + 1$$$
    • $$$x = ((x' \oplus last) \bmod 10^9) + 1$$$
    Необходимо найти минимальное число, строго большее $$$x$$$, среди всех чисел, записанных в вершинах на простом пути от вершины $$$u$$$ до вершины $$$v$$$ (включая сами вершины).

Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ (XOR в C++).

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

В первой строке входных данных заданы два целых числа $$$a_1$$$ и $$$q$$$ ($$$1 \le a_1 \le 10^9$$$, $$$1 \le q \le 5 \cdot 10^5$$$) — значение, записанное в корневой вершине, и количество запросов.

В следующих $$$q$$$ строках заданы описания запросов в зашифрованном формате, описанном в условии.

Гарантируется, что после расшифровки все параметры будут корректными: $$$1 \le p, v, u \le V$$$, а все значения $$$a$$$ и $$$x$$$ будут лежать в пределах от $$$1$$$ до $$$10^9$$$.

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

Для каждого запроса третьего типа выведите в отдельной строке одно целое число — минимальное значение на пути, которое строго больше расшифрованного $$$x$$$. Если такого числа на пути не существует, выведите -1.

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