#327 Dynamic Tree Vertex Add Subtree Sum

Statement

Statement language

You are given a tree with $N$ vertices numbered $0,1,\cdots,N-1$ . Initially, vertex $i$ has value $a_i$ .

Process $Q$ queries in order. It is guaranteed that after each query, the graph is a tree.

0 $u$ $v$ $w$ $x$ : remove the existing edge $(u,v)$ , and add the edge $(w, x)$ .

Input

The input is given in the following format.

$N\ Q$ $a_0\ a_1\ \cdots\ a_{N-1}$

Output

For each query of type 2, print the required sum of vertex values on a separate line.

Constraints

$1 \leq N,Q \leq 200\ 000$ .
$0 \leq a_i \leq 10^9$ ().

Subtasks

#	Score	Constraints
1	12	$N,Q \leq 2\ 000$ .
2	18	There are no queries of type `0`.
3	25	In every query of type `0`, the removed edge is incident to a leaf in the current tree, and that leaf is one endpoint of the newly added edge.
4	45	There are no additional constraints.

Samples

Input

7
10 100 1000 10000
1
2
3
4
1 2
1 100000
1 2
1 2 2 0
0 2
2 3 3 1
1 4

Output

In the first query, with respect to edge $(1,2)$ , the component on the side of vertex $1$ contains vertices $0,1,4$ , so the sum is $1+10+10000=10011$ .