J. Moonwalk challenge
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поскольку астронавты из миссии BubbleCup XI закончили свою миссию на Луне и являются большими поклонниками известного певца, они решили провести некоторое время перед возвращением на Землю, и, таким образом, создали так называемую игру «Moonwalk challenge».

Командам астронавтов выдаются карты кратеров на Луне и прямых двунаправленных путей от одних кратеров к другим, безопасные для «лунной походки». Каждый из этих прямых путей окрашен в один цвет, и есть единственный путь между каждым из двух кратеров. Цель игры заключается в том, чтобы найти два кратера, такие, что заданный массив цветов появляется чаще всего как непрерывный подотрезок на пути между этими двумя кратерами (пересекающиеся вхождения должны быть учтены как два различных).

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

Все цвета являются строчными буквами латинского алфавита.

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

В первой строке входного файла записано целое число $$$N$$$ $$$(2 \leq N \leq 10^5)$$$ — количество кратеров на Луне. Кратеры нумеруются числами от $$$1$$$ до $$$N$$$.

В следующих $$$N-1$$$ строках записано по три целых числа $$$u, v, L$$$ $$$(1 \leq u, v \leq N, L \in \{a, ..., z\})$$$ — описывающих прямой путь цвета $$$L$$$ между кратерами $$$u$$$ и $$$v$$$.

В следующей строке записано одно целое число $$$Q$$$ $$$(1 \leq Q \leq 10^5)$$$ — количество запросов.

В следующих $$$Q$$$ строк записано по два целых числа $$$u, v$$$ $$$(1 \leq u, v \leq N)$$$ и по одной строке $$$S$$$ $$$(|S| \leq 100)$$$, где $$$u$$$ и $$$v$$$ это два кратера для которых вам требуется подсчитать количество вхождений $$$S$$$ (представленного в виде строки) на пути между $$$u$$$ и $$$v$$$.

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

Для каждого запроса выведите количество вхождений S (представленного в виде строки) на пути между $$$u$$$ и $$$v$$$.

Пример
Входные данные
6
2 3 g
3 4 n
5 3 o
6 1 n
1 2 d
7
1 6 n
6 4 dg
6 4 n
2 5 og
1 2 d
6 5 go
2 3 g
Выходные данные
1
1
2
0
1
1
1