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

Есть массив $$$a$$$ из $$$2^{30}$$$ целых чисел, пронумерованных от $$$0$$$ до $$$2^{30}-1$$$. Изначально вы знаете, что $$$0 \leq a_i < 2^{30}$$$ ($$$0 \leq i < 2^{30}$$$), но вы не знаете эти числа. Ваша задача заключается в том, чтобы обработать все запросы двух видов:

  • 1 l r x: Вам сообщают, что исключающее ИЛИ (он же XOR) подотрезка $$$[l, r]$$$ (включительно) равно $$$x$$$. То есть $$$a_l \oplus a_{l+1} \oplus \ldots \oplus a_{r-1} \oplus a_r = x$$$, где $$$\oplus$$$ — побитовое исключающее ИЛИ. В некоторых случаях полученный запрос противоречит предыдущим запросам. В этом случае нужно проигнорировать противоречивый запрос (новый запрос).
  • 2 l r: Нужно вывести исключающее ИЛИ подмассива $$$[l, r]$$$ (включительно). Если же, используя все предыдущие запросы, ответить на этот запрос невозможно, нужно вывести $$$-1$$$.

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

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

Первая строка содержит одно целое число $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — количество запросов.

Каждая из следующих $$$q$$$ строк описывает запрос. Она содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 2$$$) — тип запроса.

Запросы закодированы следующим образом: пусть $$$last$$$ будет ответом на последний запрос второго типа, на который вы ответили (сначала $$$last = 0$$$). Если ответ был $$$-1$$$, присвойте $$$last = 1$$$.

  • Если $$$t = 1$$$, то далее следуют три целых числа $$$l'$$$, $$$r'$$$ и $$$x'$$$ ($$$0 \leq l', r', x' < 2^{30}$$$), которые значат, что вы получили обновление. Сначала сделайте следующие:
    $$$l = l' \oplus last$$$, $$$r = r' \oplus last$$$, $$$x = x' \oplus last$$$

    и, если $$$l > r$$$, поменяйте местами $$$l$$$ и $$$r$$$.

    Это значит, что исключающее ИЛИ подмассива $$$[l, r]$$$ равно $$$x$$$ (обратите внимание, что вам нужно игнорировать запросы, которые противоречат предыдущим запросам).

  • Если $$$t = 2$$$, то далее следуют два числа $$$l'$$$ и $$$r'$$$ ($$$0 \leq l', r' < 2^{30}$$$), которые значат, что вы получили запрос. Сначала сделайте следующие:
    $$$l = l' \oplus last$$$, $$$r = r' \oplus last$$$

    и, если $$$l > r$$$, поменяйте местами $$$l$$$ и $$$r$$$.

    Это значит, что нужно вывести исключающее ИЛИ подмассива $$$[l, r]$$$. Если невозможно ответить, то выведите $$$-1$$$. Не забудьте обновить значение $$$last$$$.

Гарантируется, что будет как минимум один запрос второго типа.

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

Для каждого запроса второго типа, выведите исключающее ИЛИ подмассива или $$$-1$$$, если на этот запрос невозможно ответить.

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

В первом примере, реальными запросами (перед кодированием) являются:

  • 12
  • 2 1 2
  • 2 0 1073741823
  • 1 1 2 5
  • 2 1 1
  • 2 2 2
  • 2 1 2
  • 1 2 3 6
  • 2 1 1
  • 1 1 3 0
  • 2 1 1
  • 2 2 2
  • 2 3 3
  • Ответы на первые два запроса равны $$$-1$$$ потому, что нет достаточно информации.
  • Первый запрос первого типа сообщает, что $$$a_1 \oplus a_2 = 5$$$. Обратите внимание, что до сих пор невозможно узнать значения в $$$a_1$$$ или $$$a_2$$$ (например, может быть, что $$$a_1 = 1, a_2 = 4$$$, или же $$$a_1 = 3, a_2 = 6$$$).
  • После трех запросов первого типа есть достаточно информации, чтобы узнать значения в $$$a_1, a_2, a_3$$$.

Во втором примере обратите внимание, что после двух запросов первого типа, уже известно, что $$$a_5 \oplus a_6 = 12$$$, значит третий запрос противоречит предыдущим двум, поэтому, ми его игнорируем.