Вау! Вы отлично помогли команде Р поймать всех покемонов, посланных Башем. Мяут, член частью команды Р, уже выучил человеческий язык, и теперь хочет обучиться программированию. Он согласился освободить покемонов, если Баш ответит на его вопросы.
В начале Мяут дает Башу взвешенное дерево из n вершин и последовательность a1, a2..., an, которая является перестановкой чисел 1, 2, ..., n. Теперь Мяут задает q запросов в одной из следующих форм:
- 1 l r v значит, что Баш должен посчитать
, где dist(a, b) — длина кратчайшего пути от вершины a до вершины b в данном дереве. - 2 x значит, что Баш должен поменять местами ax и ax + 1 в заданной последовательности. Новая последовательность будет использоваться для следующих запросов.
Помогите Башу ответит на запросы!
Первая строка содержит два целых числа n и q (1 ≤ n ≤ 2·105, 1 ≤ q ≤ 2·105) — количество вершин в дереве и число запросов, соответственно.
Следующая строка содержит n целых чисел — последовательность a1, a2, ..., an, являющуюся перестановкой чисел 1, 2, ..., n.
Каждая из следующих n - 1 строк содержит три целых числа u, v, и w, означающих, что существует ребро между вершинами u и v длины w, (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 106). Гарантируется, что заданный граф является деревом.
Далее следуют запросы. Каждый запрос записан в двух строках. В первой строке находится целое число t, обозначающее тип запроса. Следующая строка содержит описание запроса:
- t = 1: Вторая строка содержит три числа a, b и c (1 ≤ a, b, c < 230), используя которые, l, r и v могут быть получены по следующей формуле:
-
, -
, -
.
-
- t = 2: Вторая строка содержит целое число a (1 ≤ a < 230), используя которое, x может быть получено по следующей формуле:
-
.
-
Число ansi равно ответу на i-й запрос, можете считать, что ans0 = 0. Если i-й запрос имеет тип 2, то ansi = ansi - 1. Гарантируется, что:
- для каждого запроса типа 1: 1 ≤ l ≤ r ≤ n, 1 ≤ v ≤ n,
- для каждого запроса типа 2: 1 ≤ x ≤ n - 1.
Операция 
означает побитовое исключающее ИЛИ.
Для каждого запроса типа 1 выведите единственное число в отдельной строке — ответ на запрос.
5 5
4 5 1 3 2
4 2 4
1 3 9
4 1 4
4 5 2
1
1 5 4
1
22 20 20
2
38
2
39
1
36 38 38
23
37
28
В примере запросы следующие:
- 1 1 5 4
- 1 1 3 3
- 2 3
- 2 2
- 1 1 3 3
