問題文

Pakenomy 社は N 個の部屋と N-1 本の廊下から成り，部屋は 1 から N の，廊下は 1 から N-1 の番号がついています． 廊下 i は部屋 A_i と 部屋 B_i を双方向に結んでいます．廊下を何本か通ることで任意の 2 部屋の間を移動できるようになっています．

Pakenomy 社では多くの怪物を管理しており，緊急事態が起こるとそれらが廊下に侵入することが想定されます．イーハチはこのような状況において騒動の鎮圧を担当する職員ですが，前もって振る舞いを調べようと考えています．

イーハチが廊下 e を通るとき，体力が C_e 減ります．ここで体力が 0 以下になった場合，「蘇生」イベントが起き，体力が K になります．

Q 個の質問が与えられ，i 番目の質問は以下の通りです．

• イーハチがはじめ体力 K の状態で部屋 S_i にいて，廊下を何回か通って部屋 T_i に移動するとき，「蘇生」イベントが起こる回数は最小で何回か？

あなたの仕事は，Q 個の質問全てに答えることです．

制約

• 入力はすべて整数
• 2 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^9
• 1 \leq A_i, B_i \leq N\ (1 \leq i \leq N-1)
• 廊下を何本か通ることで任意の 2 部屋の間を移動できる
• 0 \leq C_i \leq 10^9\ (1 \leq i \leq N-1)
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq S_i, T_i \leq N\ (1 \leq i \leq Q)
• S_i \neq T_i\ (1 \leq i \leq Q)

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．

提出したソースコードの得点は，正解した小課題の点数の合計となります．

1. (5 点) N=2, Q=1 を満たす．
2. (18 点) N \leq 4000, Q \leq 4000 を満たす．
3. (12 点) N \leq 4000 を満たす．
4. (33 点) 任意の i\ (1 \leq i \leq N-1) について，A_i=i および B_i=i+1 を満たす．
5. (32 点) 追加の制約はない．

入力例 1

7 5
1 2 3
1 3 10
1 4 3
2 5 1
2 6 2
5 7 1
3
3 6
4 7
7 6

出力例 1

2
1
0

部屋 3 から 部屋 6 に向かうとき，体力は次のように変動します．

• 廊下 2 を通って体力が 5 - 10 = -5 になり，「蘇生」イベントにより体力が 5 になる．
• 廊下 1 を通って体力が 5 - 3 = 2 になる．
• 廊下 5 を通って体力が 2 - 2 = 0 になり，「蘇生」イベントにより体力が 5 になる．

部屋 4 から 部屋 7 に向かうとき，体力は次のように変動します．

• 廊下 3 を通って体力が 5 - 3 = 2 になる．
• 廊下 1 を通って体力が 2 - 3 = -1 になり，「蘇生」イベントにより体力が 5 になる．
• 廊下 4 を通って体力が 5 - 1 = 4 になる．
• 廊下 6 を通って体力が 4 - 1 = 3 になる．

部屋 7 から 部屋 6 に向かうとき，体力は次のように変動します．

• 廊下 6 を通って体力が 5 - 1 = 4 になる．
• 廊下 4 を通って体力が 4 - 1 = 3 になる．
• 廊下 5 を通って体力が 3 - 2 = 1 になる．

入力例 2

7 5
1 2 30843382
1 3 31046102
1 4 31236232
2 5 31487860
2 6 32171282
5 7 33077326
3
3 6
4 7
7 6

出力例 2

3
4
3

廊下を通るたびに蘇生することになります．

入力例 3

20 3
18 11 2
20 9 0
2 1 2
13 8 1
12 8 1
12 4 2
6 15 0
7 16 1
3 19 1
20 5 2
16 11 0
14 2 2
16 10 0
7 2 1
12 20 2
13 19 1
1 5 1
6 17 0
17 4 2
20
1 4
8 4
3 5
11 12
14 1
9 16
6 4
20 1
6 16
4 1
19 13
20 19
18 13
9 1
4 10
7 8
18 7
18 11
7 11
1 2

出力例 3

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