Teleportation in Byteland

Description:

Input:

Each 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$$$.

Output:

For each query, print one integer in a separate line — the minimum time it takes to get in the corresponding query.

Sample Input:

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

Sample Output:

1
11
14
11
13
15

Note:

In 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$$$.