G. Алфавитное дерево
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$m$$$ строк и дерево на $$$n$$$ вершинах. На каждом ребре написана какая-то буква.

Вы должны ответить на $$$q$$$ запросов. Каждый запрос описывается $$$4$$$ целыми числами $$$u$$$, $$$v$$$, $$$l$$$ и $$$r$$$. Ответом на запрос является общее количество вхождений $$$str(u,v)$$$ в строки с индексами от $$$l$$$ до $$$r$$$. $$$str(u,v)$$$ определяется как строка, составленная путем конкатенации букв, записанных на ребрах кратчайшего пути от $$$u$$$ до $$$v$$$ (в порядке их прохождения).

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

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le m,q \le 10^5$$$).

В $$$i$$$-й из следующих $$$n-1$$$ строк содержатся два целых числа $$$u_i, v_i$$$ и строчная латинская буква $$$c_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$), обозначающие ребро между вершинами $$$u_i, v_i$$$ с символом $$$c_i$$$ на нем.

Гарантируется, что эти ребра образуют дерево.

Следующие $$$m$$$ строк содержат строки, состоящие из строчных латинских букв. Общая длина этих строк не превышает $$$10^5$$$.

Затем следуют $$$q$$$ строк, каждая из которых содержит четыре целых числа $$$u$$$, $$$v$$$, $$$l$$$ и $$$r$$$ ($$$1 \le u,v \le n$$$, $$$u \neq v$$$, $$$1 \le l \le r \le m$$$), обозначающие запросы.

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

Для каждого запроса выведите одно целое число — ответ на запрос.

Примеры
Входные данные
2 5 3
1 2 a
aab
abab
aaa
b
a
2 1 1 5
1 2 1 3
2 1 3 5
Выходные данные
8
7
4
Входные данные
9 5 6
1 2 a
2 7 c
1 3 b
3 4 b
4 6 b
3 5 a
5 8 b
5 9 c
ababa
cabbb
bac
bbbac
abacaba
2 7 1 4
2 5 1 5
6 3 4 4
6 9 4 5
5 7 3 5
5 3 1 5
Выходные данные
3
4
2
1
1
10