给你 $$$m$$$ 字符串和 $$$n$$$ 节点上的树。每条边上都写有一些字母。
您必须回答 $$$q$$$ 查询。每个查询由 $$$4$$$ 整数 $$$u$$$、$$$v$$$、$$$l$$$ 和 $$$r$$$ 描述。查询的答案是索引从 $$$l$$$ 到 $$$r$$$ 的字符串中 $$$str(u,v)$$$ 出现的总数。 $$$str(u,v)$$$ 被定义为通过连接写在从 $$$u$$$ 到 $$$v$$$ 的最短路径上的边缘上的字母而形成的字符串(以便遍历它们)。
输入
输入的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$2 \le n \le 10^5$$$、$$$1 \le m,q \le 10^5$$$)。
以下 $$$n-1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$u_i、v_i$$$ 和一个小写拉丁字母 $$$c_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$),表示节点之间的边$$$u_i, v_i$$$ 上有字符 $$$c_i$$$。
保证这些边形成一棵树。
以下 $$$m$$$ 行包含由小写拉丁字母组成的字符串。这些字符串的总长度不超过$$$10^5$$$。
接下来是 $$$q$$$ 行,每行包含四个整数 $$$u$$$、$$$v$$$、$$$l$$$ 和 $$$r$$$ ($$$1 \le u,v \le n$$$, $$$u \neq v$$$, $$$1 \le l \le r \le m$$$),表示查询。
输出
对于每个查询,打印一个整数 - 查询的答案。
示例
输入 #1
2 5 3 1 2 a aab abab aaa b a 2 1 1 5 1 2 1 3 2 1 3 5
输出 #1
8 7 4
输入 #2
9 5 6 1 2 a 2 7 c 1 3 b 3 4 b 4 6 b 3 5 a 5 8 b 5 9 c ababa cabbb bac bbbac abacaba 2 7 1 4 2 5 1 5 6 3 4 4 6 9 4 5 5 7 3 5 5 3 1 5
输出 #2
3 4 2 1 1 10