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×mmodw, where x is the initial height.
- Operation 2u: 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 hi, 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≤n≤2×105.
- 2≤w≤109.
- 1≤u,v≤n.
- 1≤hi≤w.
- 1≤q≤4×105.
- 0≤d≤40.
- 0≤m<w.
### Example
Input:
51012133435123454131223112325
Output:
60
### Subtasks
- 3 of the test cases have 1≤n,q≤1000.
- 9 of the test cases have d≤1.
- 29 of the test cases have d≤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.
