Marisa's garden can be represented by a tree with $n$ vertices. At each vertex of the tree, a mushroom is planted, and a watering system is set up. Initially, the mushroom at vertex $i$ has a height of $h_i$.
The mushrooms are very special; they grow taller whenever they are watered. Furthermore, each time the height reaches $w$, a part of the mushroom of length $w$ will fall off and be harvested.
In $q$ days, Marisa can perform the following actions:
- Operation `1 u d m`: Use the watering system at vertex $u$ to water all vertices that are at a distance of no more than $d$ from $u$. The mushrooms at these vertices will have their height multiplied by $m$. In other words, the new height at these vertices will be $x \times m \mod w$, where $x$ is the initial height.
- Operation `2 u`: Find the height of the mushroom at vertex $u$.
Help Marisa handle these operations.
### Input
- The first line contains two integers $n, w$.
- The next $n-1$ lines, each containing two integers $u, v$, represent an edge of the tree.
- The next $n$ lines, where the $i$-th line contains an integer $h_i$, the height of the $i$-th mushroom.
- The next line contains an integer $q$.
- The next $q$ lines each contain an operation of one of the two types mentioned above.
### Output
- For each operation of type `2`, print the result on a new line.
### Constraints
- $2 \le n \le 2 \times 10^5$.
- $2 \le w \le 10^9$.
- $1 \le u, v \le n$.
- $1 \le h_i \le w$.
- $1 \le q \le 4 \times 10^5$.
- $0 \le d \le 40$.
- $0 \le m < w$.
### Example
Input:
```
5 10
1 2
1 3
3 4
3 5
1
2
3
4
5
4
1 3 1 2
2 3
1 1 2 3
2 5
```
Output:
```
6
0
```
### Subtasks
- $3\\%$ of the test cases have $1 \le n, q \le 1000$.
- $9\\%$ of the test cases have $d \le 1$.
- $29\\%$ of the test cases have $d \le 2$.
- $12\\%$ of the test cases have $m = 0$.
- $30\\%$ of the test cases have $m = 2$.
- The remaining test cases have no additional constraints.
