F. Teleportation in Bytelandtime limit per test8 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThere are n cities in Byteland, some of which are connected by roads, which can be traversed in any direction. The i-th road has its own hardness parameter w_i. Time spent on traversing a road with its hardness equal to w_i is \lceil\frac{w_i}{c}\rceil, where c is the current driving skill.The travel network of Byteland is a tree. In other words, between any pair of cities, there is exactly one path that passes through each city at most once.In some cities you can visit driving courses. A single course takes T time to complete, and after completing the course the driver's skill c is increased by 2 times. Notice that the time T required to complete a course is the same in all cities, and courses can be completed in the same city more than once.You need to answer the q queries: what is the minimum time it takes to get from the city a to city b if you start the travelling with driving skill c = 1?InputEach test contains multiple test cases. The first line contains a single integer t (1 \le t \le 10^4) — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers n and T (1 \le n \le 10^5, 1 \le T \le 10^6) - the number of cities and time required to complete a single driving course.The following n - 1 lines each contain three integers u_i, v_i and w_i (1 \le u_i, v_i \le n, 1 \le w_i \le 10^6, u_i \neq v_i), which mean that there exists a road connecting towns u_i and v_i with hardness equal to w_i .The next line contains a binary string s of length n, consisting only of symbols 0 and 1. If s_i = 1 (1 \le i \le n), then you can visit driving courses in the i-th city. If s_i = 0 (1 \le i \le n), then you cannot visit driving courses in the i-th city.The next line contains a single integer q (1 \le q \le 10^5) — the number of queries you are required to answer.The next q lines contain two integers a_j, b_j (1 \le a_j, b_j \le n, 1 \le j \le q) — the cities you are required to process in the j-th query.It is guaranteed that the given graph is a tree. It is guaranteed that the sum of n and the sum of q over all test cases does not exceed 10^5.OutputFor each query, print one integer in a separate line — the minimum time it takes to get in the corresponding query.ExampleInput
2
2 3
1 2 1
11
1
1 2
5 3
1 4 5
1 3 8
2 3 8
4 5 10
11001
5
1 5
2 5
5 1
3 4
4 2
Output
1
11
14
11
13
15
NoteIn the only query of the first test case, it is optimal to ignore the driving courses. Then the minimum time required is equal to the distance between vertexes 1 and 2, which is 1.In the first query of the second test case, we can spend 3 time in city number 1 visiting the driving courses, then go to vertex 5. Then the minimum time required is 3 + \lceil\frac{5}{2}\rceil + \lceil\frac{10}{2}\rceil = 11.
2
2 3
1 2 1
11
1
1 2
5 3
1 4 5
1 3 8
2 3 8
4 5 10
11001
5
1 5
2 5
5 1
3 4
4 2

1 11 14 11 13 15 
['data structures', 'dfs and similar', 'divide and conquer', 'graphs', 'shortest paths', 'trees', '*3200']