Description

Qingzhengyu is a dedicated forest ranger of YYH Land. He is responsible for maintaining the forest of YYH Land every day. At the very beginning, YYH Land has only one tree with $n$ nodes, and each node has a spiritual power value $v$.

Since YYH Land is a magical country, the trees in YYH Land also have some magical abilities. Specifically, the following operations are supported:

• 1 e
  The edge with index $e$ suddenly disappears, splitting the tree it belongs to into two trees.

• 2 u val
  The spiritual power value of the node with index $u$ becomes $val$.

• 3 u
  Qingzhengyu makes a query: find the sum of spiritual power values of the tree that contains $u$.

Now you need to help Qingzhengyu simulate the events above to understand how the forest changes.

Input Format

The first line contains $n, m$, as described above.
The second line contains $n$ numbers, the initial weights of the $n$ nodes, each within $10^3$.
The next $n - 1$ lines each contain a pair $u, v$, representing an edge. (It is guaranteed that initially it is a tree.)
The next $m$ lines contain $m$ operations:
First read an $opt$, indicating the operation type.
When $opt = 1$, read $e$, meaning to delete the $e$-th input edge. (It is guaranteed that the $e$-th edge exists.)
When $opt = 2$, read $u, val$, meaning to change the weight of node $u$ to $val$ ($val \le 1000$).
When $opt = 3$, read $u$, meaning to query the sum of node weights in the tree that contains $u$.

Output Format

For each query operation, output one line with one number representing the answer.

2 3
1 1
1 2
2 2 4
1 1
3 2

4

Hint

For $30\%$ of the testdata, $1 \leq n, m \leq 10$ holds.
For $50\%$ of the testdata, $1 \leq n, m \leq 1000$ holds.
For the other $20\%$ of the testdata, only operations $2$ and $3$ exist.
For $100\%$ of the testdata, $1 \leq n, m \leq 10^5$, and $1 \leq v, val \leq 1000$ hold.

Translated by ChatGPT 5