Gromah and LZR have entered the eighth level. There is an -vertex tree, acyclic bidirectional connected graph painted on the wall. The vertices are conveniently labeled with .

LZR finds that for every edge  in the tree, there is a non-empty set of lowercase letters  above it. Meanwhile, Gromah finds strings  and  queries  beside the tree.

Soon, LZR finds a note board saying that for each query , you may choose exactly one letter from  for all edges  in the chain  and write down the chosen letters in the order of the directed chain  to form a string , and the answer to this query is the number of schemes to choose letters so that the result string  completely contains at least one of the  given strings .

Moreover, the answers to queries may be very large, so they only need to know the answers modulo .

Please help them answer the queries to enter the next level.

输入描述:

The first line contains three positive integers , denoting the size of the tree, the number of given strings and the number of queries.

Following  lines each contains two positive integers  and a string , denoting an edge between  and  with a set  above it.

Following  lines each contains a string .

Following  lines each contains two positive integers , denoting a query .



The given graph forms a tree.

 only contains pairwise distinct lowercase letters.

 only contains lowercase letters.

 for all queries.

输出描述:

Output  lines, each contains one non-negative integer denoting the answer to corresponding query modulo .

5 2 3
1 2 nkei
1 3 ieu
2 4 nk
2 5 ne
niu
ke
3 4
4 3
3 5

0
6
3

For the first query, there is no valid scheme.

For the second query, the 6 result strings are .

For the third query, the 3 result strings are .