F. Телепортация в Байтландии
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Байтландии есть $$$n$$$ городов, некоторые пары которых соединены дорогами, по которым можно ездить в обе стороны. $$$i$$$-я дорога характеризуется сложностью проезда по ней $$$w_i$$$. Время проезда по дороге со сложностью $$$w_i$$$ равняется $$$\lceil\frac{w_i}{c}\rceil$$$ часов, где $$$c$$$ — навык вождения водителя.

Транспортная система Байтландии представляет собой дерево. Иными словами, между любой парой городов существует ровно один путь, который проходит по каждому городу не более одного раза.

В некоторых городах можно посетить курсы вождения. Если провести в таком городе, изучая курсы, $$$T$$$ часов, то навык вождения $$$c$$$ увеличивается в $$$2$$$ раза. Заметьте, что значение $$$T$$$ одинаково во всех городах, и курсы можно посещать в одном и том же городе несколько раз.

Вам нужно ответить на $$$q$$$ запросов: за какое минимальное время можно добраться из города $$$a$$$ в город $$$b$$$, если начать путь с навыком вождения $$$c = 1$$$?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$T$$$ ($$$1 \le n \le 10^5, 1 \le T \le 10^6$$$) - количество городов в Байтландии и время, которое занимает прохождение одного курса.

Каждая из следующих $$$n - 1$$$ строк содержит три целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$ ($$$1 \le u_i, v_i \le n, 1 \le w_i \le 10^6, u_i \neq v_i$$$), которые описывают дорогу между городами $$$u_i$$$ и $$$v_i$$$ со сложностью $$$w_i$$$.

Следующая строка содержит бинарную строку $$$s$$$ длины $$$n$$$, состоящую из символов $$$0$$$ и $$$1$$$. Если $$$s_i = 1$$$ ($$$1 \le i \le n$$$), то в $$$i$$$-м городе можно пройти курсы. Если $$$s_i = 0$$$ ($$$1 \le i \le n$$$), то в $$$i$$$-м городе нельзя пройти курсы.

Следующая строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество запросов, на которые вам нужно ответить.

Каждая из следующих $$$q$$$ строк содержит по два числа $$$a_j$$$ и $$$b_j$$$ ($$$1 \le a_j, b_j \le n, 1 \le j \le q$$$) — вершины, между которыми нужно найти минимальное время поездки в $$$j$$$-м запросе.

Гарантируется, что система дорог образует дерево. Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого запроса выведите одно целое число в отдельной строке — минимальное время, за которое можно добраться в соответствующем запросе.

Пример
Входные данные
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
Примечание

В первом наборе входных данных в первом запросе оптимально не проходить курсы вождения. Тогда минимальное время равно сложности дороги между городами $$$1$$$ и $$$2$$$, которое равно $$$1$$$.

Во втором наборе входных данных в первом запросе оптимально вначале пройти курсы вождения за $$$3$$$ часа в городе $$$1$$$ один раз, а потом поехать в город $$$5$$$. Тогда всего путь займёт $$$3 + \lceil\frac{5}{2}\rceil + \lceil\frac{10}{2}\rceil = 11$$$ часов.