Dynamic Tree Vertex Add Path Sum

You are given a tree with $N$ vertices. The vertices are numbered $0,1,\cdots,N-1$, and initially vertex $i$ has an integer value $a_i$.

Process the following $Q$ queries in order. The graph is always a tree while the queries are processed.

• 0 $u\ v\ w\ x$: delete the existing edge $(u,v)$ and add the edge $(w,x)$.
• 1 $p\ x$: replace with .

The input is given in the following format.

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

For each query of type 2, print one line containing the sum of the values of the vertices on the specified path in the current tree.

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