Description

Thanksone likes to eat apple too much so he planted an ordinary apple tree.

We can view the ordinary 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 $i$-th day:

1. $k_i$ apples would grow on node $x_i$.
2. A pigeon would eat $k_i$ apples from "node $x_i$ and all the neighboring nodes of $x_i$".

Finally, there will be $Q$ queries, for $i$-th query, please help Thanksone to track how many apples are there in the subtree of $x_i$.

Input

The first line contains four integers $N$, $M$, $R$ and $Q$, representing $N$ nodes, $M$ days, the root $R$ and $Q$ queries.

Following are $N-1$ lines, each contains two integers $u_i$, $v_i$, representing a directed edge pointing from $u_i$ to $v_i$.

The following one line contains $N$ integers, representing the initial amount of apples on each nodes.

Next, 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 $i$-th day.
2. If $o_i = 2$, it means that a pigeon ate $k_i$ apples from "node $x_i$ and all the neighboring nodes of $x_i$" on the $i$-th day.

Finally, the following $Q$ lines, each contains an integers $x_i$, representing the node which we want to know 

Constraints

• $1 \le N, M, Q \le 2*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$

It is guaranteed that the number of operation 2 ($o_i = 2$) won't exceed 200.
It is guaranteed that the number of apples would be nonnegative.

Subtask

1. (Testcases 1-3) $1 \le N, M, Q \le 10^3$
2. (Testcases 4-6) $o_i = 1$
3. (Testcases 7-10) No additional constraints.

Output

Output $Q$ lines, for $i$-th line, output the number of apples there are in the subtree of $x_i$.

Sample Input  Download

Sample Output  Download

Tags

Discuss