G. Яся и таинственное дерево
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Яся гуляла по лесу и совершенно случайно нашла дерево на $$$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$$$.

Обратите внимание, что запрос второго типа выполняется мысленно, то есть дерево после него никак не меняется.

Помогите Ясе ответить на все запросы.

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

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Далее следуют описания наборов.

В первой строке каждого набора даны целые числа $$$n$$$, $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — количество вершин в дереве и количество запросов.

В следующих $$$n - 1$$$ строках каждого набора даны целые числа $$$v$$$, $$$u$$$, $$$w$$$ ($$$1 \le v, u \le n$$$, $$$1 \le w \le 10^9$$$) — концы некоторого ребра в дереве и его вес.

Гарантируется, что заданный набор рёбер образует дерево.

В следующих $$$m$$$ строках каждого набора описаны запросы:

  • ^ $$$y$$$ ($$$1 \le y \le 10^9$$$) — параметр запроса первого типа;
  • ? $$$v$$$ $$$x$$$ ($$$1 \le v \le n$$$, $$$1 \le x \le 10^9$$$) — параметры запроса второго типа.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. То же самое гарантируется для $$$m$$$.

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

Для каждого набора входных данных выведите ответы на запросы второго типа.

Примеры
Входные данные
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
Входные данные
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