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

Задан неориентированный граф со взвешенными ребрами. Длина пути между двумя вершинами — побитовое исключающее ИЛИ весов его ребер (если некоторое ребро посещается несколько раз, то в результат включается то же количество раз).

Есть три вида запросов, которые необходимо обрабатывать:

  • 1 x y d — добавить ребро, соединяющее вершины x и y с весом d. Гарантируется, что до запроса не было ребра, соединяющего x и y;
  • 2 x y — удалить ребро, соединяющее вершины x и y. Гарантируется, что в графе есть такое ребро и что граф останется связным после запроса;
  • 3 x y — найти длину кратчайшего пути (не обязательно простого) от вершины x в вершину y.

Выведите ответы на все запросы типа 3.

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

В первой строке записаны два целых числа n и m (1 ≤ n, m ≤ 200000) — количество вершин и количество ребер в графе соответственно.

Затем следуют m строк, описывающие ребра графа. В каждой строке записаны три целых числа x, y и d (1 ≤ x < y ≤ n, 0 ≤ d ≤ 230 - 1). Каждая пара (x, y) встречается не более одного раза. Изначально граф связный.

В следующей строке записано одно целое число q (1 ≤ q ≤ 200000) — количество запросов.

Затем следуют q строк, описывающие запросы следующим образом:

  • 1 x y d (1 ≤ x < y ≤ n, 0 ≤ d ≤ 230 - 1) — добавить ребро, соединяющее вершины x и y с весом d. Гарантируется, что до запроса не было ребра, соединяющего x и y;
  • 2 x y (1 ≤ x < y ≤ n) — удалить ребро, соединяющее вершины x и y. Гарантируется, что в графе есть такое ребро и что граф останется связным после запроса;
  • 3 x y (1 ≤ x < y ≤ n) — найти длину кратчайшего пути (не обязательно простого) от вершины x в вершину y.

Гарантируется, что существует хотя бы один запрос типа 3.

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

Выведите ответы на все запросы типа 3 в том порядке, в котором они были заданы.

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