CF917E.Upside Down

As we all know, Eleven has special abilities. Thus, Hopper convinced her to close the gate to the Upside Down World with her mind. Upside down monsters like to move between the worlds, so they are going to attack Hopper and Eleven in order to make them stop. The monsters live in the vines. The vines form a tree with n vertices, numbered from 1 through n. There's a lowercase English letter written in each tunnel (edge).

Upside down is a magical world. There are m types of monsters in upside down, numbered from 1 through m. Each type of monster has a special word that gives them powers. The special word of type i is s__i. There are q monsters in upside down. Each one is at a junction (vertex) and is going to some other junction. If monster of type k goes from junction i to junction j, the power it gains is the number of times it sees its special world (s__k) consecutively in the tunnels. More formally:

If f(i, j) is the string we get when we concatenate the letters written in the tunnels on the shortest path from i to j, then the power the monster gains is the number of occurrences of s__k in f(i, j).

Hopper and Eleven want to get prepared, so for each monster, they want to know the power the monster gains after moving.

众所周知，十一拥有特殊能力。因此，霍珀说服她用意念关闭通往颠倒世界的传送门。颠倒世界的怪物喜欢在两个世界之间穿梭，因此它们将攻击霍珀和十一，以阻止他们关闭传送门。这些怪物栖息在藤蔓中。藤蔓构成一棵具有 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。每条隧道（即树的一条边）上都写有一个小写英文字母。

颠倒世界是一个魔法世界。其中共有 $m$ 种怪物，编号为 $1$ 到 $m$。每种怪物都拥有一个赋予其力量的特殊单词。第 $i$ 种怪物的特殊单词为 $s_i$。颠倒世界中共有 $q$ 只怪物，每只怪物位于某个路口（即某个顶点），并计划前往另一个路口。若一只类型为 $k$ 的怪物从路口 $i$ 移动到路口 $j$，则它获得的力量等于其特殊单词 $s_k$ 在所经隧道序列中连续出现的次数。更准确地说：

设 $f(i,\,j)$ 表示从 $i$ 到 $j$ 的最短路径上所有隧道（边）所写字母按顺序拼接而成的字符串，则该怪物获得的力量即为 $s_k$ 在 $f(i,\,j)$ 中作为子串出现的次数。

霍珀和十一希望提前做好准备，因此对于每只怪物，他们都想知道该怪物移动后所获得的力量值。

The first line of input contains three integers, n, m and q (2 ≤ n ≤ 105, 1 ≤ m, q ≤ 105).

The next n - 1 lines contain the tunnels (edges). Each line contains two integers v and u (1 ≤ v, u ≤ n, v ≠ u) and a lowercase English letter c, meaning there's a tunnel connecting junctions v and u written c in it. It is guaranteed that the given graph is a tree.

The next m lines contain the special words. i-th line of them contains a single string s__i (1 ≤ |s__i| ≤ 105), consisting of lowercase English letters. It is guaranteed that |_s_1| + |_s_2| + ... + |s__m| ≤ 105).

The next q lines contain the monsters. Each line contains three integers i, j and k (1 ≤ i, j ≤ n, i ≠ j, 1 ≤ k ≤ m), meaning a monster of type k is going from junction number i to junction number j.

输入的第一行包含三个整数 $n$、$m$ 和 $q$（$2 \leq n \leq 10^5$，$1 \leq m, q \leq 10^5$）。

接下来的 $n-1$ 行描述隧道（即树的边）。每行包含两个整数 $v$ 和 $u$（$1 \leq v, u \leq n$，$v \neq u$）以及一个小写英文字母 $c$，表示在结点 $v$ 与 $u$ 之间存在一条标有字母 $c$ 的隧道。保证所给图是一棵树。

接下来的 $m$ 行描述特殊单词。其中第 $i$ 行包含一个字符串 $s_i$（$1 \leq |s_i| \leq 10^5$），仅由小写英文字母组成。保证 $|s_1| + |s_2| + \dots + |s_m| \leq 10^5$。

接下来的 $q$ 行描述怪物。每行包含三个整数 $i$、$j$ 和 $k$（$1 \leq i, j \leq n$，$i \neq j$，$1 \leq k \leq m$），表示一个类型为 $k$ 的怪物正从编号为 $i$ 的结点向编号为 $j$ 的结点移动。

Print q lines. i-th line should contain a single integer, the power the i-th monster gains after moving.

输出 q 行。第 i 行应包含一个整数，表示第 i 个怪物移动后获得的力量值。