Есть массив \(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\).
Обратите внимание, что запросы в этой задаче закодированы, каждый следующий запрос вы сможете раскодировать, вычислив ответ на предыдущий.
Выходные данные
Для каждого запроса второго типа, выведите исключающее ИЛИ подмассива или \(-1\), если на этот запрос невозможно ответить.
Примечание
В первом примере, реальными запросами (перед кодированием) являются:
- 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\), значит третий запрос противоречит предыдущим двум, поэтому, ми его игнорируем.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
|
2
|
4
1 5 5 9
1 6 6 5
1 6 5 10
2 6 5
|
12
|