Недавно Мише подарили новенькое взвешенное дерево, состоящее из $$$n$$$ вершин и $$$n - 1$$$ ребра. Его друг Саша узнал о новом подарке и решил позадавать ему $$$q$$$ вопросов, связанных с этим деревом. Миша был не силен в деревьях, и поэтому попросил вас ответить на эти $$$q$$$ вопросов, которые представляют из себя следующее:
Каждый вопрос состоит из двух вершин $$$u$$$ и $$$v$$$ ($$$u \neq v$$$), а так же из целого числа $$$d$$$. Выпишем все веса ребер на простом пути от вершины $$$u$$$ до $$$v$$$ (очевидно, что такой путь всегда один): $$${w_1, w_2, ..., w_k}$$$. Необходимо посчитать количество таких индексов $$$i$$$ ($$$0 \le i \le k - 1$$$), что $$$(w_1 + w_2 +...+ w_i) * (w_{i + 1} + w_{i + 2} +...+ w_k) = d$$$.
Будем считать, что при $$$i = 0$$$, мы будем проверять на истину $$$(w_{1} + w_{2} +...+ w_k) = d$$$.
Помогите Мише с этими сложными вопросами.
На ввод в первой строке вводится число $$$n$$$ и $$$q$$$ ($$$2 \le n, q \le 10^5$$$) — число вершин в дереве и количество вопросов.
Затем следуют $$$n - 1$$$ строк, каждая из которых содержит три числа $$$u_i$$$, $$$v_i$$$ и $$$k_i$$$, описывающих ребро $$$i$$$ ($$$1 \le u_i, v_i \le n, u_i \neq v_i, |k_i| \le 1000$$$) — $$$u_i$$$ и $$$v_i$$$ - вершины, соединяемые ребром, и $$$k_i$$$ - значение, записанное на данном ребре (номера ребер $$$i$$$ нумеруются от $$$2$$$ до $$$n$$$).
Затем следует $$$q$$$ вопросов Саши, описывающихся тремя числами $$$u_j$$$, $$$v_j$$$ и $$$d_j$$$ ($$$1 \le u_j, v_j \le n, u_j \neq v_j, |d_j| \le 10^{16}$$$).
В единственной строке выведите $$$q$$$ чисел — ответы на вопросы.
Данная задача оценивается по группам тестов. Баллы за группу начисляются в том случае, если все необходимые подгруппы выполнены, и если все тесты данной подгруппы пройдены.
| Группа | Дополнительные ограничения | Баллы | Необходимые подгруппы |
| $$$0$$$ | Примеры | $$$0$$$ | — |
| $$$1$$$ | $$$n, q \le 1000$$$ | $$$15$$$ | $$$0$$$ |
| $$$2$$$ | Граф представляет из себя полное бинарное дерево* | $$$15$$$ | — |
| $$$3$$$ | для всех ребер $$$k_i = 1$$$ | $$$20$$$ | — |
| $$$4$$$ | Без дополнительных ограничений | $$$50$$$ | $$$0,1,2,3$$$ |
*Полным бинарным деревом называется дерево, все вершины которого имеют по две дочерних, кроме листьев, которые расположены на одинаковой глубине
5 21 2 12 3 11 4 14 5 13 5 44 3 2
2 2
5 21 2 02 3 03 4 04 5 01 5 01 3 0
4 2
 |  |
В первом примере, если мы выпишем веса ребер по ходу движения из вершины $$$3$$$ в $$$5$$$, то будет: {$$$1, 1, 1, 1$$$}. Два способа разбить путь так, чтобы произведение было $$$4$$$: {$$$1, 1$$$} и {$$$1, 1$$$}, $$$(1 + 1) * (1 + 1) = 4$$$; и {$$$1, 1, 1, 1$$$}, $$$(1 + 1 + 1 + 1) = 4$$$. Аналогично можно сделать и для второго вопроса в первом примере, и мы получим $$$2$$$.
