CF1608G.Alphabetic Tree

You are given $m$ strings and a tree on $n$ nodes. Each edge has some letter written on it.

You have to answer $q$ queries. Each query is described by $4$ integers $u$, $v$, $l$ and $r$. The answer to the query is the total number of occurrences of $str(u,v)$ in strings with indices from $l$ to $r$. $str(u,v)$ is defined as the string that is made by concatenating letters written on the edges on the shortest path from $u$ to $v$ (in order that they are traversed).

给你 $m$ 个字符串和一棵包含 $n$ 个节点的树。每条边上都写有一个字母。

你需要回答 $q$ 个查询。每个查询由 $4$ 个整数 $u$、$v$、$l$ 和 $r$ 描述。该查询的答案为：在下标范围为 $l$ 到 $r$（含）的字符串中，字符串 $str(u,v)$ 出现的总次数。其中，$str(u,v)$ 定义为：从节点 $u$ 到节点 $v$ 的最短路径上，按遍历顺序依次拼接各边上的字母所构成的字符串。

The first line of the input contains three integers $n$, $m$ and $q$ ($2 \le n \le 10^5$, $1 \le m,q \le 10^5$).

The $i$-th of the following $n-1$ lines contains two integers $u_i, v_i$ and a lowercase Latin letter $c_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$), denoting the edge between nodes $u_i, v_i$ with a character $c_i$ on it.

It's guaranteed that these edges form a tree.

The following $m$ lines contain the strings consisting of lowercase Latin letters. The total length of those strings does not exceed $10^5$.

Then $q$ lines follow, each containing four integers $u$, $v$, $l$ and $r$ ($1 \le u,v \le n$, $u \neq v$, $1 \le l \le r \le m$), denoting the queries.

输入的第一行包含三个整数 $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$），表示查询。

For each query print a single integer — the answer to the query.

对于每个查询，输出一个整数——该查询的答案。