description: 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).
  
  Input
  
  The first line of the input contains three integers n, m and q (2 ≤ n ≤ 10^5, 1 ≤ m,q ≤ 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 ≤ u_i, v_i ≤ n, u_i ≠ 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 ≤ u,v ≤ n, u ≠ v, 1 ≤ l ≤ r ≤ m), denoting the queries. 
  
  Output
  
  For each query print a single integer — the answer to the query.
  
  Examples
  
  Input
  
  
  2 5 3
  1 2 a
  aab
  abab
  aaa
  b
  a
  2 1 1 5
  1 2 1 3
  2 1 3 5
  
  
  Output
  
  
  8
  7
  4
  
  
  Input
  
  
  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
  
  
  Output
  
  
  3
  4
  2
  1
  1
  10
solution: #include <bits/stdc++.h>
  using namespace std;
  template <typename T>
  inline void Read(T &x) {
    int c = getchar();
    bool f = false;
    for (x = 0; !isdigit(c); c = getchar())
      if (c == '-') f = true;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    if (f) x = -x;
  }
  inline int read() {
    int s = 0, ch = getchar(), w = 1;
    while (ch < '0' || ch > '9') {
      if (ch == '-') w = -1;
      ch = getchar();
    }
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
  }
  inline long long Read() {
    long long s = 0;
    int ch = getchar(), w = 1;
    while (ch < '0' || ch > '9') {
      if (ch == '-') w = -1;
      ch = getchar();
    }
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
  }
  inline void swap(int &x, int &y) { x ^= y ^= x ^= y; }
  const int kcz = 998244353;
  const int G = 3, GI = 332748118;
  inline void add(int &x, const int &y) { x += y, x >= kcz ? x -= kcz : 1; }
  inline int Add(const int &x, const int &y) {
    return x + y >= kcz ? x + y - kcz : x + y;
  }
  inline int qpow(int x, int y = kcz - 2) {
    int ret = 1;
    while (y) {
      if (y & 1) ret = int((long long)(ret) * (x) % kcz);
      x = int((long long)(x) * (x) % kcz), y >>= 1;
    }
    return ret;
  }
  inline int qpow(int x, int y, const int &ljc) {
    int ret = 1;
    while (y) {
      if (y & 1) ret = int(1ll * ret * x % ljc);
      x = int(1ll * x * x % ljc), y >>= 1;
    }
    return ret;
  }
  mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
  const int N = 4e5 + 10;
  namespace MAIN {
  int sit[N], sitr[N];
  int pos[N];
  char str[N];
  pair<int, int> chain[N], Chain[N];
  int cx;
  namespace Tr {
  vector<pair<int, int> > G[N];
  int sz[N], son[N], dep[N], fa[N], ch[N];
  void dfs(int x, int fax, int depx) {
    sz[x] = 1, fa[x] = fax, dep[x] = depx;
    for (auto [tox, c] : G[x]) {
      if (tox == fax) continue;
      dfs(tox, x, depx + 1), ch[tox] = c, sz[x] += sz[tox];
      if (sz[tox] > sz[son[x]]) son[x] = tox;
    }
  }
  int top[N], dfn[N], idx, pos[N];
  void dfs(int x, int topx) {
    top[pos[dfn[x] = ++idx] = x] = topx;
    if (son[x]) dfs(son[x], topx);
    for (auto [tox, c] : G[x]) {
      if (tox == fa[x] || tox == son[x]) continue;
      dfs(tox, tox);
    }
  }
  inline void gchain(int u, int v) {
    int A = 0, B = 0;
    while (top[u] != top[v]) {
      if (dep[top[u]] > dep[top[v]])
        chain[++A] = make_pair(sitr[u], sitr[top[u]]), u = fa[top[u]];
      else
        Chain[++B] = make_pair(sit[top[v]], sit[v]), v = fa[top[v]];
    }
    if (dep[u] < dep[v]) chain[++A] = make_pair(sit[u] + 1, sit[v]);
    if (dep[u] > dep[v]) chain[++A] = make_pair(sitr[u], sitr[v] - 1);
    for (int i = B; i >= 1; i--) chain[++A] = Chain[i];
    cx = A;
  }
  }  // namespace Tr
  namespace SA {
  int str[N];
  int rnk[N], buc[N], sa[N], hei[N], fr[N], sc[N], n, m;
  inline void get_SA() {
    m = 10000;
    for (int i = 1; i <= n; i++) buc[fr[i] = str[i]]++;
    for (int i = 2; i <= m; i++) buc[i] += buc[i - 1];
    for (int i = n; i; i--) sa[buc[fr[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1) {
      int num = 0;
      for (int i = n - k + 1; i <= n; i++) sc[++num] = i;
      for (int i = 1; i <= n; i++)
        if (sa[i] > k) sc[++num] = sa[i] - k;
      memset(buc, 0, sizeof(buc));
      for (int i = 1; i <= n; i++) buc[fr[i]]++;
      for (int i = 2; i <= m; i++) buc[i] += buc[i - 1];
      for (int i = n; i; i--) sa[buc[fr[sc[i]]]--] = sc[i], sc[i] = 0;
      swap(fr, sc);
      fr[sa[1]] = 1;
      num = 1;
      for (int i = 2; i <= n; i++)
        fr[sa[i]] =
            (sc[sa[i]] == sc[sa[i - 1]] && sc[sa[i] + k] == sc[sa[i - 1] + k])
                ? num
                : ++num;
      if (num == n) break;
      m = num;
    }
  }
  inline void get_hei() {
    int k = 0;
    rnk[sa[1]] = 1;
    for (int i = 2; i <= n; i++)
      rnk[sa[i]] = rnk[sa[i - 1]] +
                   (fr[sa[i]] != fr[sa[i - 1]] || sc[sa[i]] != sc[sa[i - 1]]);
    for (int i = 1; i <= n; i++) {
      if (rnk[i] == 1) continue;
      if (k) k--;
      int j = sa[rnk[i] - 1];
      while (j + k <= n && i + k <= n && str[i + k] == str[j + k]) k++;
      hei[rnk[i]] = k;
    }
  }
  int st[N][21];
  inline void PRE() {
    for (int i = 1; i <= n; i++) st[i][0] = hei[i];
    for (int j = 1; j <= 20; j++)
      for (int i = 1; i + (1 << j) - 1 <= n; i++)
        st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  }
  int Lg[N];
  inline int query_min(int l, int r) {
    int k = Lg[r - l];
    return min(st[l][k], st[r - (1 << k) + 1][k]);
  }
  inline int LCP(const int &l, const int &r) {
    if (l == r) return n - l + 1;
    int x = rnk[l], y = rnk[r];
    if (x > y) swap(x, y);
    return query_min(x + 1, y);
  }
  inline void pre() {
    for (int i = 2; i <= n; i++) Lg[i] = Lg[i >> 1] + 1;
    str[n + 1] = 26, get_SA(), get_hei(), PRE();
  }
  inline bool small(int p) {
    p = sa[p];
    for (int i = 1; i <= cx; i++) {
      int s = n - p, t = chain[i].second - chain[i].first + 1,
          _ = min({s, t, LCP(p, chain[i].first)});
      if (_ != min(s, t)) return str[p + _] < str[chain[i].first + _];
      if (_ == s && _ == t) return i != cx;
      if (_ < t) return 1;
      p += t;
    }
    return 0;
  }
  inline bool match(int p) {
    p = sa[p];
    for (int i = 1; i <= cx; i++) {
      int s = n - p, t = chain[i].second - chain[i].first + 1,
          _ = min({s, t, LCP(p, chain[i].first)});
      if (_ < t) return 0;
      if (_ == s) return i == cx;
      p += t;
    }
    return 1;
  }
  inline int gpos() {
    int l = 1, r = n, ret = 0;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (small(mid))
        l = mid + 1, ret = mid;
      else
        r = mid - 1;
    }
    return ret;
  }
  inline int findl(int r) {
    int l = 1, ret = r + 1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (match(mid))
        r = mid - 1, ret = mid;
      else
        l = mid + 1;
    }
    return ret;
  }
  inline int findr(int l) {
    int r = n, ret = l - 1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (match(mid))
        l = mid + 1, ret = mid;
      else
        r = mid - 1;
    }
    return ret;
  }
  }  // namespace SA
  vector<int> Q[N];
  int n, m, q;
  int tr[N];
  inline void modify(const int &x, const int &y) {
    for (int i = x; i <= SA::n; i += ((i) & -(i))) tr[i] += y;
  }
  inline int query(const int &x) {
    int ret = 0;
    for (int i = x; i; i -= ((i) & -(i))) ret += tr[i];
    return ret;
  }
  int ans[N];
  pair<int, int> que[N];
  inline void MAIN() {
    n = read(), m = read(), q = read();
    for (int i = 1; i < n; i++) {
      int u = read(), v = read();
      char sss[5];
      scanf("%s", sss + 1);
      Tr::G[u].emplace_back(make_pair(v, sss[1])),
          Tr::G[v].emplace_back(make_pair(u, sss[1]));
    }
    for (int i = 1; i <= m; i++) {
      scanf("%s", str + 1);
      int t = int(strlen(str + 1));
      for (int j = 1; j <= t; j++)
        SA::n++, SA::str[SA::n] = str[j], pos[SA::n] = i;
      SA::str[++SA::n] = 'z' + 1;
    }
    Tr::dfs(1, 0, 1), Tr::dfs(1, 1), Tr::ch[1] = 'a' - 1;
    for (int i = 1; i <= Tr::idx; i++) {
      int p = Tr::pos[i];
      SA::n++, sit[p] = SA::n, SA::str[SA::n] = Tr::ch[p];
    }
    for (int i = Tr::idx; i >= 1; i--) {
      int p = Tr::pos[i];
      SA::n++, sitr[p] = SA::n, SA::str[SA::n] = Tr::ch[p];
    }
    SA::pre();
    for (int T = 1; T <= q; T++) {
      int u = read(), v = read(), L = read(), R = read();
      Tr::gchain(u, v), que[T] = make_pair(L, R);
      int x = SA::gpos();
      int l = x + 1, r = SA::findr(x + 1);
      if (l <= r) Q[l - 1].push_back(-T), Q[r].push_back(T);
    }
    for (int i = 1; i <= SA::n; i++) {
      int p = SA::sa[i];
      if (pos[p]) modify(pos[p], 1);
      for (auto x : Q[i])
        ans[abs(x)] += (x > 0 ? 1 : -1) *
                       (query(que[abs(x)].second) - query(que[abs(x)].first - 1));
    }
    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
  }
  }  // namespace MAIN
  int main() {
    int Case = 1;
    while (Case--) MAIN::MAIN();
    return 0;
  }
  