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

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.