CF757G.Can Bash Save the Day?

Whoa! You did a great job helping Team Rocket who managed to capture all the Pokemons sent by Bash. Meowth, part of Team Rocket, having already mastered the human language, now wants to become a master in programming as well. He agrees to free the Pokemons if Bash can answer his questions.

Initially, Meowth gives Bash a weighted tree containing n nodes and a sequence _a_1, _a_2..., a__n which is a permutation of 1, 2, ..., n. Now, Mewoth makes q queries of one of the following forms:

• 1 l r v: meaning Bash should report , where dist(a, b) is the length of the shortest path from node a to node b in the given tree.
• 2 x: meaning Bash should swap a__x and a__x + 1 in the given sequence. This new sequence is used for later queries.

Help Bash to answer the questions!

哇！你出色地帮助了火箭队，他们成功捕获了巴什派出的所有宝可梦。火箭队成员喵喵已经掌握了人类语言，现在还想成为编程大师。他同意：如果巴什能回答他的问题，就释放所有宝可梦。

初始时，喵喵给巴什一棵含 $ n $ 个节点的带权树，以及一个序列 $ a_1, a_2, \dots, a_n $，该序列是 $ 1, 2, \dots, n $ 的一个排列。接着，喵喵提出 $ q $ 个查询，查询类型为以下两种之一：

• 1 l r v：要求巴什计算 ，其中 $ \text{dist}(a, b) $ 表示给定树中节点 $ a $ 到节点 $ b $ 的最短路径长度。
• 2 x：要求巴什在给定序列中交换 $ a_x $ 与 $ a_{x+1} $。此后所有查询均基于该更新后的序列。

请帮助巴什回答这些问题！

The first line contains two integers n and q (1 ≤ n ≤ 2·105, 1 ≤ q ≤ 2·105) — the number of nodes in the tree and the number of queries, respectively.

The next line contains n space-separated integers — the sequence _a_1, _a_2, ..., a__n which is a permutation of 1, 2, ..., n.

Each of the next n - 1 lines contain three space-separated integers u, v, and w denoting that there exists an undirected edge between node u and node v of weight w, (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ w ≤ 106). It is guaranteed that the given graph is a tree.

Each query consists of two lines. First line contains single integer t, indicating the type of the query. Next line contains the description of the query:

• t = 1: Second line contains three integers a, b and c (1 ≤ a, b, c < 230) using which l, r and v can be generated using the formula given below:
  • ,
  • ,
  • .
• t = 2: Second line contains single integer a (1 ≤ a < 230) using which x can be generated using the formula given below:
  • .

The ans__i is the answer for the i-th query, assume that _ans_0 = 0. If the i-th query is of type 2 then ans__i = ans__i - 1. It is guaranteed that:

• for each query of type 1: 1 ≤ l ≤ r ≤ n, 1 ≤ v ≤ n,
• for each query of type 2: 1 ≤ x ≤ n - 1.

The operation means bitwise exclusive OR.

第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 2 \cdot 10^5$，$1 \leq q \leq 2 \cdot 10^5$）—— 分别表示树中节点的数量和查询的数量。

第二行包含 $n$ 个用空格分隔的整数 —— 序列 $a_1,\,a_2,\,\dots,\,a_n$，它是 $1,\,2,\,\dots,\,n$ 的一个排列。

接下来的 $n-1$ 行，每行包含三个用空格分隔的整数 $u$、$v$ 和 $w$，表示在节点 $u$ 与节点 $v$ 之间存在一条权重为 $w$ 的无向边（$1 \leq u,\,v \leq n$，$u \ne v$，$1 \leq w \leq 10^6$）。保证所给图是一棵树。

每个查询由两行组成。第一行包含一个整数 $t$，表示查询类型；第二行包含该查询的具体描述：

• $t = 1$：第二行包含三个整数 $a$、$b$ 和 $c$（$1 \leq a,\,b,\,c < 2^{30}$），用于通过下方公式生成 $l$、$r$ 和 $v$：
  • ,
  • ,
  • .
• $t = 2$：第二行包含一个整数 $a$（$1 \leq a < 2^{30}$），用于通过下方公式生成 $x$：
  • .

记 $ans_i$ 为第 $i$ 个查询的答案，并设 $ans_0 = 0$。若第 $i$ 个查询为类型 2，则 $ans_i = ans_{i-1}$。保证满足：

• 对于每个类型 1 的查询：$1 \leq l \leq r \leq n$，$1 \leq v \leq n$；
• 对于每个类型 2 的查询：$1 \leq x \leq n - 1$。

符号 表示按位异或（bitwise exclusive OR）运算。

For each query of type 1, output a single integer in a separate line, denoting the answer to the query.

对于每个类型为 1 的查询，在单独一行中输出一个整数，表示该查询的答案。

In the sample, the actual queries are the following:

• 1 1 5 4
• 1 1 3 3
• 2 3
• 2 2
• 1 1 3 3

在样例中，实际的查询如下：

• 1 1 5 4
• 1 1 3 3
• 2 3
• 2 2
• 1 1 3 3