Problem Description

There is a tree. Each edge has two weights $D_i$ and $T_i$. You are given $Q$ operations. There are two types of operations:

0 x y t: change the $T_i$ value of the edge between $x$ and $y$ to $t$.

1 x y: query the cost from $x$ to $y$.

Define the cost from $x$ to $y$ as follows: given a parameter $G$ (the same for all queries), node $x$ needs to transport some amount of value to node $y$. Each time it passes an edge with weights $D_i$ and $T_i$, the transported value decreases by $T_i$, and then a cost equal to $D_i$ times the current transported value is incurred. When the transport reaches node $y$, if the remaining value is exactly $G$, then the total incurred cost is defined as the cost from $x$ to $y$.

You need to compute the cost for each query. Since the cost may be large, output it modulo $10^9+7$.

Input Format

The first line contains two integers $N, G$.

Lines $2 \sim N$ each contain four integers $A_i, B_i, D_i, T_i$, meaning there is an edge between $A_i$ and $B_i$ in the tree, with edge weights $D_i$ and $T_i$.

Line $N+1$ contains an integer $Q$, the number of operations.

The next $Q$ lines each contain one operation, in the format described above.

Output Format

Output several lines. For each query operation, you need to output the cost. Print one answer per line.

6 2
1 2 2 1
2 3 1 2
2 4 2 3
4 5 2 2
4 6 1 4
3
1 3 6
0 4 5 5
1 2 5

23
18

4 3
1 2 3 0
2 3 1 0
3 4 4 0
1
1 1 4

24

Hint

Constraints

This problem uses bundled testdata.

Subtask 0 is the sample.

Subtask 1 (5 pts): only query operations, each node degree is at most $2$, and $T_i = 0$.

Subtask 2 (9 pts): only query operations, and $T_i = 0$.

Subtask 3 (12 pts): only query operations, $D_i = 1$, and all $T_i$ are equal.

Subtask 4 (17 pts): only query operations, and each node degree is at most $2$.

Subtask 5 (20 pts): each node degree is at most $2$.

Subtask 6 (18 pts): $N, Q \leq 5000$.

Subtask 7 (19 pts): no special constraints.

It is guaranteed that $2 \leq N \leq 10^5$, $1 \leq Q \leq 10^5$, $1 \leq A_i, B_i \leq N$, $1 \leq D_i, G \leq 10^9$, and $0 \leq T_i \leq 10^9$.

Translated by ChatGPT 5