Problem Description

Pakenomy Corporation consists of $ N $ rooms and $ N-1 $ corridors, with rooms numbered from $ 1 $ to $ N $ and corridors numbered from $ 1 $ to $ N-1 $. Corridor $ i $ connects room $ A_i $ and room $ B_i $ bidirectionally. It is possible to travel between any two rooms by traversing some number of corridors.

Pakenomy Corporation manages many monsters, and in an emergency, it is anticipated that they will invade the corridors. Ihatchi is an employee responsible for suppressing such disturbances, but he wants to investigate his behavior in advance.

When Ihatchi traverses corridor $ e $, his health decreases by $ C_e $. If his health drops to $ 0 $ or below, a "resurrection" event occurs, and his health is restored to $ K $.

You are given $ Q $ queries, where the $ i $-th query is as follows:

• Starting with health $ K $ in room $ S_i $, how many times does the "resurrection" event occur at a minimum when Ihatchi travels through some corridors to reach room $ T_i $?

Your task is to answer all $ Q $ queries.

Input Format

The input is provided from standard input in the following format:

$ N $ $ K $ $ A_1 $ $ B_1 $ $ C_1 $ : $ A_{N-1} $ $ B_{N-1} $ $ C_{N-1} $ $ Q $ $ S_1 $ $ T_1 $ : $ S_Q $ $ T_Q $

Output Format

Output $ Q $ lines. The $ i $-th line should contain the answer to the $ i $-th query.

Sample Input and Output

Sample Input #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

Sample Output #1

2
1
0

Sample Input #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

Sample Output #2

3
4
3

Sample Input #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

Sample Output #3

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

Notes/Hints

Constraints

• All input values are integers.
• $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)$
• It is possible to travel between any two rooms by traversing some number of corridors.
• $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)$

Partial Points

This problem is divided into several sub-tasks, and you are considered to have solved a sub-task if you correctly answer all test cases for that sub-task.

The score of your submitted source code is the sum of the points for the sub-tasks you solved.

1. (5 points) $ N=2, Q=1 $
2. (18 points) $N \leq 4000, Q \leq 4000$
3. (12 points) $N \leq 4000$
4. (33 points) For any $i \ (1 \leq i \leq N-1)$, $ A_i=i $ and $ B_i=i+1 $
5. (32 points) No additional constraints.

Sample Explanation 1

When traveling from room $ 3 $ to room $ 6 $, health changes as follows:
- Traversing corridor $ 2 $ reduces health to $ 5 - 10 = -5 $, triggering the "resurrection" event restoring health to $ 5 $.
- Traversing corridor $ 1 $ reduces health to $ 5 - 3 = 2 $.
- Traversing corridor $ 5 $ reduces health to $ 2 - 2 = 0 $, triggering the "resurrection" event restoring health to $ 5 $.

When traveling from room $ 4 $ to room $ 7 $, health changes as follows:
- Traversing corridor $ 3 $ reduces health to $ 5 - 3 = 2 $.
- Traversing corridor $ 1 $ reduces health to $ 2 - 3 = -1 $, triggering the "resurrection" event restoring health to $ 5 $.
- Traversing corridor $ 4 $ reduces health to $ 5 - 1 = 4 $.
- Traversing corridor $ 6 $ reduces health to $ 4 - 1 = 3 $.

When traveling from room $ 7 $ to room $ 6 $, health changes as follows:
- Traversing corridor $ 6 $ reduces health to $ 5 - 1 = 4 $.
- Traversing corridor $ 4 $ reduces health to $ 4 - 1 = 3 $.
- Traversing corridor $ 5 $ reduces health to $ 3 - 2 = 1 $.

Sample Explanation 2

Each traversal of a corridor results in a resurrection.

见题面 Input 部分

见题面 Output 部分