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 hi.
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 1udm: 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.
