A14741 | 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).

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.

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