Thanksone is a CS student who likes to eat apple very much so he plants a magical apple tree. We can view the magical apple tree as a tree with $N$ nodes and the root is $R$. Initially, there would be some apples on each of the nodes. Then, during the following $M$ days, one of the two things might happen on the $ith$ day:
Please help Thanksone to track how much apples are there after $M$ days.
The first line contains three integers $N$, $M$ and $R$, representing $N$ nodes, $M$ days and the root $R$.
Following are $N-1$ lines, each contains two integers $u_i$, $v_i$, representing an edge between $u_i$ and $v_i$.
The following one line contains $N$ integers, representing the initial amount of apples on each nodes.
Finally, the following $M$ lines, each contains three integers $o_i$, $k_i$, $x_i$.
1. If $o_i = 1$, it means that $k_i$ apples grew on node $x_i$ on the $ith$ day.
2. If $o_i = 2$, it means that a pigeon ate $k_i$ apples from each node in the subtree of $x_i$ on the $ith$ day.
Contraints
$1 \le N, M \le 5*10^5$
$1 \le R \le N$
$o_i = {1, 2}$
$1 \le k_i \le 1*10^9$
$1 \le x_i \le N$
Subtask
1. (Testcases 1-3) $1 \le N, M \le 10^3$
2. (Testcases 4-6) $o_i = 1$
3. (Testcases 7-10) No additional constraints.
Output the numbers of apples on $N$ nodes in a line. (Output a whitespace after every integer, including the last one)