Problem Background

JOISC2022 D3T2

Problem Description

JOI-kun has years of experience growing vegetables in his own garden and now plans to manage the IOI Farm.

The IOI Farm consists of $N$ plots of land connected by $N-1$ bidirectional roads, numbered from $1$ to $N-1$. The $i$-th road connects land $A_i$ and $B_i$. Any two plots of land can be reached from one another via these roads. Each plot of land is equipped with a sprinkler that can water nearby lands.

JOI-kun plans to grow JOI-grain at the IOI Farm. JOI-grain is a peculiar crop whose height changes instantly when watered. However, it is also a delicate plant. If its height reaches or exceeds $L$, the top part of length $L$ will immediately break off. JOI-kun will harvest the fallen part.

Initially, JOI-kun plants a JOI-grain of height $H_j$ on land $j$, and over the next $Q$ days, he will tend to these JOI-grains. On the $k$-th day, JOI-kun will perform one of the following two operations:

• Operation $1$: JOI-kun uses the sprinkler on land $X_k$ to water lands within a distance of $D_k$ from land $X_k$, causing the height of JOI-grains on these lands to multiply by $W_k$. Due to the continuous breaking, if a JOI-grain of original height $h$ is watered, its height becomes $hW_k \bmod L$.
• Operation $2$: JOI-kun measures the height of the JOI-grain on land $X_k$.

The distance between land $x$ and land $y$ is defined as the minimum number of roads needed to travel from land $x$ to land $y$.

JOI-kun wants the JOI-grains to grow as planned, so he needs to calculate the expected height of the JOI-grain for each Operation $2$.

Input Format

The first line contains two integers $N$ and $L$, representing the number of plots of land and the breaking threshold of JOI-grain.

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

The next $N$ lines each contain one integer $H_i$, representing the initial height of the JOI-grain on each land.

The next line contains one integer $Q$, representing the number of operations.

The next $Q$ lines, the $k$-th line starts with $T_k$, indicating the type of operation. If $T_k=1$, it is Operation $1$, followed by three integers $X_k$, $D_k$, and $W_k$, representing the sprinkler's land, watering radius, and growth parameter. If $T_k=2$, it is Operation $2$, followed by one integer $X_k$, representing the land where the height needs to be measured.

Output Format

For each Operation $2$, output one integer representing the expected height of the JOI-grain.

Sample Input and Output

Input Sample #1

4 7
1 2
2 3
3 4
1
1
1
1
11
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
1 4 10 2
2 1
2 2
2 3
2 4

Output Sample #1

4
2
2
1
1
4
4
2

Input Sample #2

6 10
5 6
1 2
1 4
2 6
3 6
9
2
3
4
9
1
10
1 5 1 7
2 4
1 4 1 9
1 5 0 7
2 1
1 1 1 3
1 6 1 4
2 5
2 4
2 3

Output Sample #2

4
1
4
8
2

Input Sample #3

8 10
1 3
3 5
4 7
6 7
4 5
7 8
2 4
5
8
6
4
6
2
9
3
11
1 2 2 0
2 1
1 6 1 0
2 4
2 6
1 5 2 0
2 8
1 7 2 0
2 6
2 7
2 4

Output Sample #3

5
0
0
3
0
0
0

Notes/Hints

[Sample Explanation #1]

Initially, JOI-kun plants JOI-grains of height $1$ on all lands.

On the first day, JOI-kun uses the sprinkler on land $2$, affecting lands $1, 2, 3$, multiplying their heights by $2$, resulting in heights $2, 2, 2, 1$.

On the second day, JOI-kun uses the sprinkler on land $1$, affecting land $1$, multiplying its height by $2$, resulting in heights $4, 2, 2, 1$.

On the seventh day, JOI-kun uses the sprinkler on land $4$, affecting lands $1, 2, 3, 4$, multiplying their heights by $2$. The first JOI-grain's height becomes $8$, breaking off, resulting in heights $1, 4, 4, 2$.

This sample satisfies the constraints of subtasks $1, 5, 6$.

[Sample Explanation #2]

On the first day, JOI-kun uses the sprinkler on land $5$, affecting lands $5, 6$, multiplying their heights by $7$, resulting in heights $63, 7$. Therefore, the JOI-grain on land $5$ will break continuously, resulting in a height of $3$.

This sample satisfies the constraints of subtasks $1, 2, 3, 6$.

[Sample Explanation #3]

This sample satisfies the constraints of subtasks $1, 3, 4, 6$.

[Data Range]

For all data, the following constraints are satisfied:

• $2 \leq N \leq 200000$
• $2 \leq L \leq 10^9$
• $1 \leq A_i < B_i \leq N$ $(i \in [1, N-1])$
• Any two lands can be reached from one another via roads.
• $0 \leq H_j < L$ $(1 \leq j \leq N)$
• $1 \leq Q \leq 400000$
• $T_k$ is either $1$ or $2$
• For $T_k = 1$ $(k \in [1, Q])$, $1 \leq X_k \leq N$, $0 \leq D_k \leq 40$, $0 \leq W_k < L$
• For $T_k = 2$ $(k \in [1, Q])$, $1 \leq X_k \leq N$

Detailed subtask additional constraints and scores are as follows:

见题面 Input 部分

见题面 Output 部分