There is a rooted tree with root $1$, where each node has a weight.

There are $m$ operations of three types:

$1\ x\ y\ w$: Add $w$ to the weights of all nodes on the path between $x$ and $y$ (where $w = \pm 1$);

$2\ x\ y$: Query how many nodes on the path between $x$ and $y$ have a weight $> 0$;

$3\ x$: Query how many nodes in the subtree of $x$ have a weight $> 0$.

Input

The first line contains three integers $n, m, T$, representing the number of nodes in the tree, the number of operations, and whether the input is encrypted.

The next $n-1$ lines each contain two integers $x, y$, representing an edge between nodes $x$ and $y$.

The next line contains $n$ integers, where the $i$-th integer represents the initial weight of node $i$.

The next $m$ lines follow the format described above.

If $T=1$, then for each $x, y$ read in these $m$ lines, you must XOR them with $last\_ans$ to obtain the actual input, where $last\_ans$ is the answer to the previous query operation. If there is no previous query operation, $last\_ans = 0$.

Output

For each query operation, output one line containing the answer.

Examples

Input 1

5 5 0
1 2
1 3
3 4
3 5
1 0 0 0 0
2 2 5
3 3
1 2 5 1
2 2 5
3 3

Output 1

1
0
4
2

Constraints

• For all data, $1 \le n \le 10^5$, $1 \le m \le 10^5$, $-10^9 \le$ node weight $\le 10^9$.
• Subtask 1 (3 pts): $n, m \le 5000$.
• Subtask 2 (10 pts): The given tree is a chain.
• Subtask 3 (15 pts): $T=0$, and there are no type $3$ operations.
• Subtask 4 (15 pts): $T=0$.
• Subtask 5 (10 pts): $n, m \le 50000$.
• Subtask 6 (47 pts): No additional constraints.

Time limit: $\texttt{2s}$

Memory limit: $\texttt{512MB}$