Яся гуляла по лесу и совершенно случайно нашла дерево на \(n\) вершинах. Дерево — это связный неориентированный граф, в котором отсутствуют циклы.
Рядом с деревом девочка нашла древний манускрипт, на котором записаны \(m\) запросов. Запросы бывают двух видов.
Первый вид запросов описывается числом \(y\). Вес каждого ребра в дереве заменяется на побитовое исключающее «ИЛИ» веса этого ребра и числа \(y\).
Второй вид описывается вершиной \(v\) и числом \(x\). Яся выбирает вершину \(u\) (\(1 \le u \le n\), \(u \neq v\)) и мысленно проводит в дереве двунаправленное ребро веса \(x\) из \(v\) в \(u\).
Затем Яся находит простой цикл в получившемся графе и считает побитовое исключающее «ИЛИ» от всех рёбер на нём. Она хочет выбрать такую вершину \(u\), чтобы посчитанное значение было максимально. Это посчитанное значение и будет ответом на запрос. Можно показать существование и единственность такого цикла в указанных ограничениях (независимо от выбора \(u\)). Если ребро между \(v\) и \(u\) уже существовало, простым циклом будет путь \(v \to u \to v\).
Обратите внимание, что запрос второго типа выполняется мысленно, то есть дерево после него никак не меняется.
Помогите Ясе ответить на все запросы.
Выходные данные
Для каждого набора входных данных выведите ответы на запросы второго типа.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3 7
1 2 1
3 1 8
^ 5
? 2 9
^ 1
? 1 10
^ 6
? 3 1
? 2 9
5 6
1 2 777
3 2 2812
4 1 16
5 3 1000000000
^ 4
? 3 123
? 5 1000000000
^ 1000000000
? 1 908070
? 2 1
|
13 15 11 10
1000000127 2812 999756331 999999756
|
|
2
|
3
8 4
8 6 3
6 3 4
2 5 4
7 6 2
7 1 10
4 1 4
5 1 2
^ 4
^ 7
? 7 8
? 4 10
5 6
3 1 4
2 3 9
4 3 6
5 2 10
? 5 7
^ 1
^ 8
? 4 10
? 1 9
? 3 6
4 2
2 1 4
4 3 5
2 3 4
^ 13
? 1 10
|
14 13
13 8 11 11
10
|