众所周知,十一拥有特殊能力。于是,霍珀说服她用意念关闭了颠倒世界的大门。颠倒的怪物喜欢在世界之间移动,所以他们要攻击霍珀和十一,以阻止他们。怪物住在藤蔓里。这些藤蔓形成一棵有 n 个顶点的树,编号从 1 到 n。每个隧道(边缘)上都写有一个小写英文字母。
颠倒是一个神奇的世界。颠倒的怪物有 m 种,编号从 1 到 m。每种类型的怪物都有一个特殊的词赋予它们力量。类型i的特殊词是si。颠倒有q个怪物。每个节点都位于一个交汇点(顶点),并将前往另一个交汇点。如果类型k的怪物从结点i走到结点j,它获得的力量就是它在隧道中连续看到它的特殊世界(sk)的次数。更正式地说:
如果f(i, j)是我们将隧道中写的字母按照从i到j的最短路径连接起来得到的字符串,那么怪物获得的力量就是f(i, j)中sk出现的次数。
霍珀和十一想要做好准备,因此对于每个怪物,他们想知道怪物移动后获得的力量。
输入
输入的第一行包含三个整数,n、m 和 q (2 ≤ n ≤ 105, 1 ≤ m, q ≤ 105)。
接下来的 n - 1 行包含隧道(边缘)。每行包含两个整数v和u(1≤v,u≤n,v≠u)和一个小写英文字母c,表示有一条隧道连接v和u交叉点,其中写为c。保证给定的图是一棵树。
接下来的 m 行包含特殊单词。其中第 i 行包含单个字符串 si (1 ≤ |si| ≤ 105),由小写英文字母组成。保证|s1| + |s2| + ... + |sm| ≤ 105)。
接下来的 q 行包含怪物。每行包含三个整数 i、j 和 k(1 ≤ i、j ≤ n、i ≠ j、1 ≤ k ≤ m),这意味着类型 k 的怪物将从编号 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
输出 #1
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 2 0 0 0 1 1