canbashsavetheday

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, \ldots, a_n\) which is a permutation of \(1, 2, \ldots, n\). Now, Mewoth makes \(q\) queries of one of the following forms:

• \(1\) \(l\) \(r\) \(v\): meaning Bash should report \(\displaystyle \sum_{i = l}^{r}{\textrm{dist}(a_i, v)}\), where \(\textrm{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!

Input format

The first line contains two integers \(n\) and \(q\) \((1 \leq n \leq 2 \times 10^5, 1 \leq q \leq 2 \times 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, \ldots, a_n\) which is a permutation of \(1, 2, \ldots, 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 \leq u, v \leq n, u \neq v, 1 \leq w \leq 10^6)\). It is guaranteed that the given graph is a tree.

Each query consists of one line. The first integer is \(t\), indicating the type of the query. Some integers follow:

• t = 1: Three integers \(l\), \(r\) and \(v\) \((1 \leq l \leq r \leq n, 1 \leq v \leq n)\).
• t = 2: A single integer \(x\) \((1 \leq x \leq n - 1)\).

Output format

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

Limits

Subtask #	Score	Constraints
1	8	\(n, q \leq 2000\)
2	15	\(l = 1\) \(r = n\)
3	20	\(n, q \leq 50000\) All queries are of type \(1\).
4	21	All queries are of type \(1\).
5	36	No additional constraints

Samples

Sample Input 1	Sample Output 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 1 3 3 2 3 2 2 1 1 3 3	23 37 28