24949번 - Sprinkler 서브태스크다국어

JOI-kun has years of experience of growing vegetables in his home vegetable garden. Now he is planning to manage IOI Farm.

IOI Farm consists of $N$ lands, numbered from $1$ to $N$. There are $N - 1$ roads connecting with lands, numbered from $1$ to $N - 1$. The road $i$ ($1 ≤ i ≤ N - 1$) connects the land $A_i$ and the land $B_i$ bidirectionally. It is possible to move from any land to any other land by passing through roads. There is a sprinkler in every land of IOI Farm. Using a sprinkler, we can spray water on surrounding lands.

JOI-kun is planning to grow JOI millets in IOI Farm. JOI millet is a curious plant. If we give water, the height of a JOI millet changes immediately. But, JOI millet is a weak plant. If the height of a JOI millet becomes larger than or equal to $L$, the top part of length $L$ of the JOI millet is broken immediately. JOI-kun will harvest the broken parts of JOI millets.

In the beginning, JOI-kun plants a JOI millet of height $H_j$ in the land $j$ ($1 ≤ j ≤ N$). After that, for $Q$ days, JOI-kun will take care of the JOI millets everyday. On the $k$-th day ($1 ≤ k ≤ Q$), JOI-kun takes one of the following actions.

• Type 1 : JOI-kun uses the sprinkler of the land $X_k$ to give water to every land whose distance from the land $X_k$ is less than or equal to $D_k$. If water is given on a land, the JOI millet in that land grows, and its height is multiplied by $W_k$. But, the top part of length $L$ of the JOI millet is broken immediately, when the height becomes larger than or equal to $L$. Therefore, if JOI-kun gives water to a JOI millet of height $h$, the height of the JOI millet finally becomes “the remainder of $h × W_k$ when divided by $L$.”
• Type 2 : JOI-kun measures the height of a JOI millet in the land $X_k$.

Here, the distance from the land $x$ ($1 ≤ x ≤ N$) to the land $y$ ($1 ≤ y ≤ N$) is the minimum number of roads we have to pass through when we move from the land $x$ to the land $y$.

JOI-kun wants to see that the JOI millets are grown up as planned. For this purpose, he wants to calculate the height of a JOI millet measured by each action of Type 2 in advance.

Write a program which, given information of IOI Farm and JOI-kun’s plan, calculates the height of a JOI millet measured by each action of Type 2 taken by JOI-kun.

Read the following data from the standard input. Given values are all integers.

$\begin{align*}& N\,L \\ & A_1 \, B_1 \\ & A_2 \, B_2 \\ & \vdots \\ & A_{N-1} \, B_{N-1} \\ & H_1 \\ & H_2 \\ & \vdots \\ & H_N \\ & Q \\ & \text{(Query }1\text{)} \\ & \text{(Query }2\text{)} \\ & \vdots \\ & \text{(Query }Q\text{)}  \end{align*}$

Each $\text{(Query }k\text{)}$ ($1 ≤ k ≤ Q$) consists of space separated integers. Let $T_k$ be the first integer of $\text{(Query }k\text{)}$. The content of this line is one of the following.

• If $T_k = 1$, this line also contains three more space separated integers $X_k$, $D_k$, $W_k$, in this order. This means JOI-kun takes an action of Type 1 on the $k$-th day, JOI-kun gives water to every land whose distance from the land $X_k$ is less than or equal to $D_k$, and the height of a JOI millet is multiplied by $W_k$ after water is given.
• If $T_k = 2$, this line also contains one more integer $X_k$. This means JOI-kun takes an action of Type 2 on the k-th day, and JOI-kun measures the height of a JOI millet in the land $X_k$.

For each action of Type 2 (i.e., for each $k$ ($1 ≤ k ≤ Q$) with $T_k = 2$), write the height of a JOI millet in the land $X_k$ measured by the action of Type 2 on the $k$-th day to the standard output, in this order. The outputs should be separated by line breaks.

• $2 ≤ N ≤ 200\,000$.
• $2 ≤ L ≤ 1\,000\,000\,000$ ($= 10^9$).
• $1 ≤ A_i < B_i ≤ N$ ($1 ≤ i ≤ N - 1$).
• It is possible to move from any land to any other land by passing through roads.
• $0 ≤ H_j ≤ L - 1$ ($1 ≤ j ≤ N$).
• $1 ≤ Q ≤ 400\,000$.
• $T_k$ is either $1$ or $2$ ($1 ≤ k ≤ Q$).
• For every $k$ ($1 ≤ k ≤ Q$) with $T_k = 1$, the following inequalities are satisfied: $1 ≤ X_k ≤ N$, $0 ≤ D_k ≤ 40$, $0 ≤ W_k ≤ L - 1$.
• For every $k$ ($1 ≤ k ≤ Q$) with $T_k = 2$, the inequality $1 ≤ X_k ≤ N$ is satisfied.