Все знают, что Одиннадцать обладает некоторыми сверхспособностями. Поэтому Хоппер уговорила ее закрыть врата на Обратную сторону силой мысли. Монстры с Обратной стороны любят перемещаться между мирами, поэтому они собираются атаковать Хоппер и Одиннадцать, чтобы остановить их. Монстры живут на дереве из n вершин, пронумерованных от 1 до n. На каждом ребре написана строчная латинская буква.
Обратная сторона — магический мир. В нем живут m видов монстров, пронумерованных от 1 до m. У каждого вида монстров есть специальное слово, которое дает ему силу. Специальное слово вида i равно si. Всего на Обратной стороне q монстров. Каждый сейчас находится в одной вершине и собирается дойти до некоторой другой вершины. Если монстр типа k идет от вершины i до вершины j, его сила увеличивается на количество раз, когда он видел свое специальное слово (sk) как подстроку на своем пути. Более формально:
Пусть f(i, j) — строка, которую мы получим, если выпишем все буквы на ребрах на кратчайшем пути из i в j. Тогда сила монстра увеличивается на количество вхождений sk в f(i, j).
Хоппер и Одиннадцать хотят подготовиться, поэтому для каждого монстра они хотят определить силу, которую приобретет монстр после передвижения.
Выходные данные
Выведите q строк. В i-й из этих строк выведите силу i-го монстра после передвижения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 4 5
1 6 b
2 3 a
1 2 b
5 3 b
4 5 b
a
b
bb
aa
1 2 1
6 2 3
1 6 2
4 5 4
1 6 2
|
0
1
1
0
1
|
|
2
|
10 6 7
1 3 s
10 1 d
2 6 s
5 2 d
7 4 l
8 9 d
8 10 l
7 2 d
8 7 l
dl
dssld
d
d
l
sl
4 5 4
3 7 5
10 6 2
3 1 4
7 5 6
10 9 4
9 8 4
|
2
2
0
0
0
1
1
|