Вам даны \(m\) строк и дерево на \(n\) вершинах. На каждом ребре написана какая-то буква.
Вы должны ответить на \(q\) запросов. Каждый запрос описывается \(4\) целыми числами \(u\), \(v\), \(l\) и \(r\). Ответом на запрос является общее количество вхождений \(str(u,v)\) в строки с индексами от \(l\) до \(r\). \(str(u,v)\) определяется как строка, составленная путем конкатенации букв, записанных на ребрах кратчайшего пути от \(u\) до \(v\) (в порядке их прохождения).
Выходные данные
Для каждого запроса выведите одно целое число — ответ на запрос.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|