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,\hspace{0.17em}{a}_2,\dots ,\hspace{0.17em}{a}_n$ which is a permutation of $1,\hspace{0.17em}2,\hspace{0.17em}\dots ,\hspace{0.17em}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\text{dist}(a_i,v)}$, where $\text{dist}(a,\hspace{0.17em}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\hspace{0.17em}+\hspace{0.17em}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\hspace{0.17em}\le \hspace{0.17em}n\hspace{0.17em}\le 2\times {10}^5,1\hspace{0.17em}\le \hspace{0.17em}q\hspace{0.17em}\le \hspace{0.17em}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,\hspace{0.17em}{a}_2,\hspace{0.17em}\dots ,\hspace{0.17em}{a}_n$ which is a permutation of $1,\hspace{0.17em}2,\hspace{0.17em}\dots ,\hspace{0.17em}n$.

Each of the next $n\hspace{0.17em}-\hspace{0.17em}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\hspace{0.17em}\le \hspace{0.17em}u,\hspace{0.17em}v\hspace{0.17em}\le \hspace{0.17em}n,u\hspace{0.17em}\ne \hspace{0.17em}v,1\hspace{0.17em}\le \hspace{0.17em}w\hspace{0.17em}\le \hspace{0.17em}{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\le l\le r\le n,1\le v\le n)$.
• t = 2: A single integer $x$ $(1\le x\le 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\le 2000$
2	15	$l=1$ $r=n$
3	20	$n,q\le 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