Cruel Borders

The states of the European Union can be modeled as a graph in which there is exactly one path between any two states, so the graph is a tree. The states are numbered from 1 to $n$, and Croatia is state 1. This year Mr. Malnar presides over the European Union, so many meetings must be organized. The representatives are odd: they like to travel in groups. On the way to Croatia, everyone passing through a state first gathers in that state. Then they continue to the next state as one group together with that state's representative. There more people join, and this repeats until everyone meets at node 1. (See the explanation of the first sample for details.)

A customs duty on people has been introduced in the European Union. Each state $i$ has a duty $c_i$, and every person entering that state must pay it. The state's own representatives do not pay duty in their own state. The customs officers are cynical about the Union. In each state, the largest group arriving together is charged double the duty. If several groups are equally large, the group coming from the state with the smallest number is charged.

Your program must support three operations:

• $1$ $v$: If a meeting were held right now, how much money would the representative of state $v$ have to pay?
• $2$ $v$ $c$: State $v$ changes its duty to $c$.
• $3$ $v$ $c$: A new state appears. Its number $k$ is the smallest positive integer that is not yet the number of an existing state. Its duty is $c$, and it is connected to state $v$.

The first line contains $n$ and $q$ ($1 \le n, q \le 10^5$), the initial number of states and the number of operations. The second line contains $n$ integers, where the $i$-th integer is $c_i$ ($0 \le c_i \le 10^9$), the duty of state $i$. Each of the next $n-1$ lines contains $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), meaning states $u_i$ and $v_i$ are connected by an edge.

Let $lastans$ be the answer to the most recent operation of type 1, with $lastans = 0$ if there has been no such operation. Let $k$ be the largest state number that exists so far. Let $\oplus$ denote bitwise xor.

If the $i$-th event is of type 1, the line contains $1$ $v'$ ($0 \le v' \le 10^{18}$, $1 \le v \le k$), and $v = v' \oplus lastans$.

If the $i$-th event is of type 2 or type 3, the line contains $2$ $v'$ $c'$ or $3$ $v'$ $c'$ ($0 \le v', c' \le 10^{18}$, $1 \le v \le k$, $0 \le c \le 10^9$), and $v = v' \oplus lastans$, $c = c' \oplus lastans$.

For the $i$-th operation of type 1, print the answer on the $i$-th line.

Explanation of the first input: The fourth operation is the first of type 1, so $lastans = 0$, and that operation makes no change. The representative of state 2 travels to state 3 and pays the double duty 6, because it is the only group entering that city and therefore the largest. Now the representatives from states 2 and 3 enter state 6 together. That group has two people, while the group from state 7 has only one, so they pay the double duty, meaning the representative of state 2 pays the duty 6. After that, the representatives of states 2, 3, 6, and 7 travel together to state 1 and pay the double duty as the largest group, so the representative of state 2 pays 8. The total is $6 + 6 + 8 = 20$.

In the fifth operation $lastans = 20$, so $v = 16 \oplus 20 = 5$. The representative of state 5 travels alone to state 1. It is not the largest group, so it pays the single duty $4$.