問題文

$1$ から $N$ までの番号がつけられた $N$ 個の頂点を持つ木があります。 この木の $i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結び、その色は $c_i$、長さは $d_i$ です。 ここで各辺の色は $1$ 以上 $N-1$ 以下の整数で表されており、同じ整数は同じ色に、異なる整数は異なる色に対応します。

以下の $Q$ 個の問いに答えてください。

• 問 $j$ ($1 \\leq j \\leq Q$): 色 $x_j$ のすべての辺の長さが $y_j$ に変更されたと仮定して、二頂点 $u_j, v_j$ 間の距離を求めよ。(辺の長さの変更はこれ以降の問いには影響しない。)

制約

• $2 \\leq N \\leq 10^5$
• $1 \\leq Q \\leq 10^5$
• $1 \\leq a_i, b_i \\leq N$
• $1 \\leq c_i \\leq N-1$
• $1 \\leq d_i \\leq 10^4$
• $1 \\leq x_j \\leq N-1$
• $1 \\leq y_j \\leq 10^4$
• $1 \\leq u_j < v_j \\leq N$
• 与えられるグラフは木である。
• 入力中のすべての値は整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$ $a_1$ $b_1$ $c_1$ $d_1$ $:$ $a_{N-1}$ $b_{N-1}$ $c_{N-1}$ $d_{N-1}$ $x_1$ $y_1$ $u_1$ $v_1$ $:$ $x_Q$ $y_Q$ $u_Q$ $v_Q$

出力

$Q$ 行出力せよ。$j$ 行目 ($1 \\leq j \\leq Q$) に問 $j$ への回答を出力すること。

入力例 1

5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4

出力例 1

130
200
60

この入力中のグラフは次のようなものです。

ここで、色 $1$ の辺は赤い実線で、色 $2$ の辺は緑の太線で、色 $4$ の辺は青い破線で示されています。

• 問 $1$: 色 $1$ のすべての辺の長さが $100$ に変更されたと仮定すると、頂点 $1, 4$ 間の距離は $100 + 30 = 130$ です。
• 問 $2$: 色 $1$ のすべての辺の長さが $100$ に変更されたと仮定すると、頂点 $1, 5$ 間の距離は $100 + 100 = 200$ です。
• 問 $3$: 色 $3$ のすべての辺の長さが $1000$ に変更されたと仮定すると (そのような辺は存在しません)、頂点 $3, 4$ 間の距離は $20 + 10 + 30 = 60$ です。この問いでは色 $1$ の辺の長さが元に戻っていることに注意してください。