Problem Statement

There is a tree with $N$ vertices numbered $1$ to $N$. The $i$-th edge connects vertices $a_i$ and $b_i$. Each vertex $i$ has a weight $W_i$ and a color $C_i \in \lbrace 0,1 \rbrace$. Process $Q$ queries. There are three types of queries as follows.

• 1 v: Change $C_v$ to $1 - C_v$ for vertex $v$.
• 2 v x: Change $W_v$ to $W_v + x$ for vertex $v$.
• 3 v: Let $c$ be the color of vertex $v$. Output the sum of weights of all vertices reachable from vertex $v$ by traveling only through vertices of color $c$ (including vertex $v$ itself).

Constraints

• $1 \leq N \leq 3 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq W_i \leq 10^9$
• $C_i \in \lbrace 0,1 \rbrace$
• $1 \leq a_i \lt b_i \leq N$
• The input graph is a tree.
• $1 \leq v \leq N$
• $1 \leq x \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format, where $\mathrm{query}_i$ denotes the $i$-th query:

N Q
W_1 W_2 \dots W_N
C_1 C_2 \dots C_N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in one of the following formats:

1 v

2 v x

3 v

Output

Let $m$ be the number of type-$3$ queries given. Output $m$ lines. The $i$-th line should contain the answer for the $i$-th type-$3$ query.