{"raw_statement":[{"iden":"statement","content":"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).\n\n<center>![image](https://espresso.codeforces.com/066866a19462ac485ac3911e51a91db4817e7c17.png)</center>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:\n\nIf _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_).\n\nHopper and Eleven want to get prepared, so for each monster, they want to know the power the monster gains after moving."},{"iden":"input","content":"The first line of input contains three integers, _n_, _m_ and _q_ (2 ≤ _n_ ≤ 105, 1 ≤ _m_, _q_ ≤ 105).\n\nThe 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.\n\nThe 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).\n\nThe 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_."},{"iden":"output","content":"Print _q_ lines. _i_\\-th line should contain a single integer, the power the _i_\\-th monster gains after moving."},{"iden":"examples","content":"Input\n\n6 4 5\n1 6 b\n2 3 a\n1 2 b\n5 3 b\n4 5 b\na\nb\nbb\naa\n1 2 1\n6 2 3\n1 6 2\n4 5 4\n1 6 2\n\nOutput\n\n0\n1\n1\n0\n1\n\nInput\n\n10 6 7\n1 3 s\n10 1 d\n2 6 s\n5 2 d\n7 4 l\n8 9 d\n8 10 l\n7 2 d\n8 7 l\ndl\ndssld\nd\nd\nl\nsl\n4 5 4\n3 7 5\n10 6 2\n3 1 4\n7 5 6\n10 9 4\n9 8 4\n\nOutput\n\n2\n2\n0\n0\n0\n1\n1"}],"translated_statement":[{"iden":"statement","content":"众所周知，Eleven 拥有特殊能力。因此，Hopper 说服她用意念关闭通往颠倒世界的门户。颠倒世界的怪物喜欢在两个世界间移动，因此它们将攻击 Hopper 和 Eleven，以迫使他们停止。这些怪物生活在藤蔓中。藤蔓形成一棵包含 #cf_span[n] 个顶点的树，顶点编号从 #cf_span[1] 到 #cf_span[n]。每条边（隧道）上都写有一个小写英文字母。\n\n颠倒世界是一个魔法世界。其中共有 #cf_span[m] 种怪物，编号从 #cf_span[1] 到 #cf_span[m]。每种怪物都拥有一个赋予其力量的特殊单词，第 #cf_span[i] 种怪物的特殊单词为 #cf_span[si]。颠倒世界中有 #cf_span[q] 只怪物，每只都位于一个节点（顶点），并正前往另一个节点。如果类型为 #cf_span[k] 的怪物从节点 #cf_span[i] 移动到节点 #cf_span[j]，它获得的力量等于它在路径上连续看到其特殊单词（#cf_span[sk]）的次数。更正式地：\n\n如果 #cf_span[f(i, j)] 表示从 #cf_span[i] 到 #cf_span[j] 的最短路径上所有边上的字母按顺序拼接形成的字符串，则该怪物获得的力量等于 #cf_span[sk] 在 #cf_span[f(i, j)] 中出现的次数。\n\nHopper 和 Eleven 希望做好准备，因此对于每只怪物，他们需要知道它移动后获得的力量。\n\n输入的第一行包含三个整数 #cf_span[n, m] 和 #cf_span[q]（#cf_span[2 ≤ n ≤ 105]，#cf_span[1 ≤ m, q ≤ 105]）。\n\n接下来的 #cf_span[n - 1] 行描述隧道（边）。每行包含两个整数 #cf_span[v] 和 #cf_span[u]（#cf_span[1 ≤ v, u ≤ n]，#cf_span[v ≠ u]）以及一个小写英文字母 #cf_span[c]，表示存在一条连接节点 #cf_span[v] 和 #cf_span[u] 的隧道，其上写有字母 #cf_span[c]。保证给定的图是一棵树。\n\n接下来的 #cf_span[m] 行包含特殊单词。第 #cf_span[i] 行包含一个字符串 #cf_span[si]（#cf_span[1 ≤ |si| ≤ 105]），由小写英文字母组成。保证 #cf_span[|s1| + |s2| + ... + |sm| ≤ 105]。\n\n接下来的 #cf_span[q] 行描述怪物。每行包含三个整数 #cf_span[i], #cf_span[j] 和 #cf_span[k]（#cf_span[1 ≤ i, j ≤ n]，#cf_span[i ≠ j]，#cf_span[1 ≤ k ≤ m]），表示一只类型为 #cf_span[k] 的怪物从节点 #cf_span[i] 移动到节点 #cf_span[j]。\n\n请输出 #cf_span[q] 行。第 #cf_span[i] 行应包含一个整数，表示第 #cf_span[i] 只怪物移动后获得的力量。"},{"iden":"input","content":"输入的第一行包含三个整数 #cf_span[n, m] 和 #cf_span[q]（#cf_span[2 ≤ n ≤ 105]，#cf_span[1 ≤ m, q ≤ 105]）。接下来的 #cf_span[n - 1] 行描述隧道（边）。每行包含两个整数 #cf_span[v] 和 #cf_span[u]（#cf_span[1 ≤ v, u ≤ n]，#cf_span[v ≠ u]）以及一个小写英文字母 #cf_span[c]，表示存在一条连接节点 #cf_span[v] 和 #cf_span[u] 的隧道，其上写有字母 #cf_span[c]。保证给定的图是一棵树。接下来的 #cf_span[m] 行包含特殊单词。第 #cf_span[i] 行包含一个字符串 #cf_span[si]（#cf_span[1 ≤ |si| ≤ 105]），由小写英文字母组成。保证 #cf_span[|s1| + |s2| + ... + |sm| ≤ 105]。接下来的 #cf_span[q] 行描述怪物。每行包含三个整数 #cf_span[i], #cf_span[j] 和 #cf_span[k]（#cf_span[1 ≤ i, j ≤ n]，#cf_span[i ≠ j]，#cf_span[1 ≤ k ≤ m]），表示一只类型为 #cf_span[k] 的怪物从节点 #cf_span[i] 移动到节点 #cf_span[j]。"},{"iden":"output","content":"请输出 #cf_span[q] 行。第 #cf_span[i] 行应包含一个整数，表示第 #cf_span[i] 只怪物移动后获得的力量。"},{"iden":"examples","content":"输入\n6 4 5\n1 6 b\n2 3 a\n1 2 b\n5 3 b\n4 5 b\nab\nbb\naa\n1 2 1\n6 2 3\n1 6 2\n4 5 4\n1 6 2\n输出\n0\n1\n1\n0\n1\n\n输入\n10 6 7\n1 3 s\n10 1 d\n2 6 s\n5 2 d\n7 4 l\n8 9 d\n8 10 l\n7 2 d\n8 7 l\ndldss\nldd\nls\nl\n4 5 4\n3 7 5\n10 6 2\n3 1 4\n7 5 6\n10 9 4\n9 8 4\n输出\n2\n2\n0\n0\n0\n1\n1"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ |V| = n $, where each edge $ e \\in E $ is labeled with a lowercase English letter.  \nLet $ S = \\{s_1, s_2, \\dots, s_m\\} $ be a set of $ m $ special strings (monster types), where $ s_i \\in \\Sigma^* $ and $ \\sum_{i=1}^m |s_i| \\leq 10^5 $.  \nFor any pair of vertices $ (u, v) $, let $ f(u, v) \\in \\Sigma^* $ denote the string formed by concatenating the edge labels along the unique simple path from $ u $ to $ v $ in $ T $.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq m, q \\leq 10^5 $  \n3. $ \\sum_{i=1}^m |s_i| \\leq 10^5 $  \n4. For each query $ (i, j, k) $: $ 1 \\leq i, j \\leq n $, $ i \\neq j $, $ 1 \\leq k \\leq m $  \n\n**Objective**  \nFor each query $ (i, j, k) $, compute the number of occurrences of $ s_k $ as a contiguous substring in $ f(i, j) $.  \nThat is, output:  \n$$\n\\text{count}(s_k, f(i, j)) = \\left| \\left\\{ p \\in \\{1, \\dots, |f(i,j)| - |s_k| + 1\\} \\mid f(i,j)[p:p+|s_k|-1] = s_k \\right\\} \\right|\n$$","simple_statement":null,"has_page_source":false}