JOI Valley Management

JOI has many years of experience in growing vegetables in his own garden and now plans to manage the IOI Farm. The IOI Farm consists of $N$ lands connected by $N-1$ bidirectional roads. The $i$-th road connects lands $A_i$ and $B_i$, and any two lands are reachable from one another via these roads.

Each land has a sprinkler. When a sprinkler is used, it waters all lands within a certain distance. JOI plants a special crop called JOI Valley on each land. This crop behaves strangely: as soon as it is watered, its height is immediately updated. However, JOI Valley is fragile. If its height reaches or exceeds $L$, then the top portion of length $L$ breaks off and falls. JOI collects the fallen part.

Initially, on the $j$-th land, a JOI Valley plant is planted with height $H_j$. Over the next $Q$ days, JOI will take care of these crops. On the $k$-th day, he performs one of the following two operations:

• Operation 1: JOI uses the sprinkler on land $X_k$ to water all lands whose distance from land $X_k$ is at most $D_k$. For every affected crop with current height $h$, its height is updated to \[ h \leftarrow (h \times W_k) \bmod L \] (i.e. its height becomes the remainder when $hW_k$ is divided by $L$).
• Operation 2: JOI measures the height of the JOI Valley crop on land $X_k$.

The distance between two lands $x$ and $y$ is defined as the minimum number of roads one must traverse to go from $x$ to $y$.

JOI wishes to predict the heights that will be measured in each Operation 2. Help him by simulating the operations.

inputFormat

The input begins with a line containing three integers: $N$, $Q$, and $L$.

The next $N-1$ lines each contain two integers $A_i$ and $B_i$, representing a road connecting lands $A_i$ and $B_i$.

The following line contains $N$ integers: $H_1, H_2, \dots, H_N$, the initial heights of the crops.

Then $Q$ lines follow. Each line describes an operation:

• For an operation of type 1, the line contains: 1 X D W. This indicates that the sprinkler on land $X$ waters every land at a distance at most $D$, updating the height of the crop there by setting \(h \leftarrow (h \times W) \bmod L\).
• For an operation of type 2, the line contains: 2 X. This means you should output the current height of the crop on land $X$.

outputFormat

For each operation of type 2, output the current height of the crop on the specified land on a new line.

sample

5 5 10
1 2
1 3
2 4
2 5
1 2 3 4 5
2 3
1 2 1 3
2 2
1 1 2 2
2 5

3
6
0