# Can Bash Save the Day?

## 题意翻译

一棵 $n$ 个点的树和一个排列 $p_i$，边有边权，支持两种操作：
- `l r x`，询问 $\sum\limits _{i=l}^{r} dis(p_i,x)$。
- `x`，交换 $p_x,p_{x+1}$。
$n,q\leq 2\times 10^5$，强制在线。

## 题目描述

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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF757G/ea8253b2e126f0f9a4f7e577c28110ed4a318c5a.png), 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!

## 输入输出格式

### 输入格式

The first line contains two integers $ n $ and $ q $ ( $ 1<=n<=2·10^{5} $ , $ 1<=q<=2·10^{5} $ ) — 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<=10^{6} $ ). 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<2^{30} $ ) using which $ l $ , $ r $ and $ v $ can be generated using the formula given below:
- ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF757G/8aee8013a9e038e56ef819c034e3f838e39c5b69.png),
- ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF757G/8a6ca8e44774777b9443d62d70704ae5a8cbd864.png),
- ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF757G/2332d289771b1a35329bc48f3b3da516601f653d.png).
- t = 2: Second line contains single integer $ a $ ( $ 1<=a<2^{30} $ ) using which $ x $ can be generated using the formula given below:
- ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF757G/eb2a03b6eebdb7c4867abe4c7844cc3adf9f4a53.png).
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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF757G/4298d47c0191af3c0a3103f431751061bc7e2362.png) operation means bitwise exclusive OR.

### 输出格式

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

## 输入输出样例

### 输入样例 #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
```

### 输出样例 #1

```
23
37
28
```

## 说明

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