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;
  const int N = 2e5 + 5, L = 17, D = 1e9 + 7, W = 27;
  char s[N];
  pair<int, int> seg[N];
  int nex_r[N], dy_r[N];
  vector<pair<int, char>> lk[N];
  int dep[N], f[N][L];
  long long rt_to[N][L], to_rt[N][L], pow_W[N], h[N][L];
  void dfs(int x, int fr) {
    f[x][0] = fr;
    dep[x] = dep[fr] + 1;
    for (int i = 1; i < L; ++i) {
      int y = f[x][i - 1];
      f[x][i] = f[y][i - 1];
      rt_to[x][i] = (rt_to[y][i - 1] * pow_W[1 << (i - 1)] + rt_to[x][i - 1]) % D;
      to_rt[x][i] = (to_rt[x][i - 1] * pow_W[1 << (i - 1)] + to_rt[y][i - 1]) % D;
    }
    for (auto pr : lk[x]) {
      int y;
      char c;
      tie(y, c) = pr;
      if (y != fr) {
        rt_to[y][0] = to_rt[y][0] = c;
        dfs(y, x);
      }
    }
  }
  namespace BIT {
  int c[N];
  void add(int x) {
    for (int i = x; i < N; i += i & -i) ++c[i];
  }
  int query(int x) {
    int ans = 0;
    for (int i = x; i; i -= i & -i) ans += c[i];
    return ans;
  }
  int query(int l, int r) { return query(r) - query(l - 1); }
  }  // namespace BIT
  namespace SA {
  int qa[2][N];
  int sa[N], h[N], *rk = qa[0], *tmp = qa[1];
  int cnt[N];
  void get_sa(int n) {
    for (int i = 1; i <= n; ++i) ++cnt[s[i]];
    for (int i = 1; i <= 128; ++i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; --i) sa[cnt[s[i]]--] = i;
    int m = 1;
    rk[sa[1]] = 1;
    for (int i = 2; i <= n; ++i) {
      if (s[sa[i]] != s[sa[i - 1]]) ++m;
      rk[sa[i]] = m;
    }
    for (int l = 1; m < n; l *= 2) {
      int top = 0;
      for (int i = n - l + 1; i <= n; ++i) tmp[++top] = i;
      for (int i = 1; i <= n; ++i)
        if (sa[i] > l) tmp[++top] = sa[i] - l;
      memset(cnt + 1, 0, m * sizeof(int));
      for (int i = 1; i <= n; ++i) ++cnt[rk[i]];
      for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
      for (int i = n; i >= 1; --i) sa[cnt[rk[tmp[i]]]--] = tmp[i];
      swap(rk, tmp);
      m = 1;
      rk[sa[1]] = 1;
      for (int i = 2; i <= n; ++i) {
        int now = sa[i], last = sa[i - 1];
        if (tmp[now] != tmp[last] || tmp[now + l] != tmp[last + l]) ++m;
        rk[now] = m;
      }
    }
    int l = 0;
    for (int i = 1; i <= n; ++i) {
      if (l) --l;
      int now = rk[i];
      while (s[i + l] == s[sa[now + 1] + l]) ++l;
      h[now] = l;
    }
  }
  };  // namespace SA
  int qu[N], qv[N];
  vector<pair<int, int>> lkq[N];
  int ans[N], tot;
  int get_lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int j = L - 1; j >= 0; --j)
      if (dep[x] - dep[y] & (1 << j)) x = f[x][j];
    if (x == y) return x;
    for (int j = L - 1; j >= 0; --j)
      if (f[x][j] != f[y][j]) {
        x = f[x][j];
        y = f[y][j];
      }
    return f[x][0];
  }
  int query(int u, int v) {
    int lca = get_lca(u, v);
    int du = dep[u] - dep[lca], dv = dep[v] - dep[lca];
    static int _v[L];
    for (int j = 0; j < L; ++j)
      if (dv & (1 << j)) {
        _v[j] = v;
        v = f[v][j];
      }
    auto cmp_le = [&](const pair<int, int>& seg) -> bool {
      int l, r;
      tie(l, r) = seg;
      int nu = u;
      for (int j = 0; j < L; ++j)
        if (du & (1 << j)) {
          if (h[l][j] != to_rt[nu][j]) {
            while (j) {
              --j;
              if (h[l][j] == to_rt[nu][j]) {
                l += 1 << j;
                nu = f[nu][j];
              }
            }
            return h[l][0] < to_rt[nu][0];
          }
          l += 1 << j;
          nu = f[nu][j];
        }
      for (int j = L - 1; j >= 0; --j)
        if (dv & (1 << j)) {
          int nv = _v[j];
          if (h[l][j] != rt_to[nv][j]) {
            while (j) {
              --j;
              if (h[l][j] == rt_to[f[nv][j]][j]) {
                l += 1 << j;
              } else
                nv = f[nv][j];
            }
            return h[l][0] < rt_to[nv][0];
          }
          l += 1 << j;
        }
      return 0;
    };
    auto cmp_eq = [&](const pair<int, int>& seg) -> bool {
      int l, r;
      tie(l, r) = seg;
      int nu = u;
      for (int j = 0; j < L; ++j)
        if (du & (1 << j)) {
          if (h[l][j] != to_rt[nu][j]) return 0;
          l += 1 << j;
          nu = f[nu][j];
        }
      for (int j = L - 1; j >= 0; --j)
        if (dv & (1 << j)) {
          int nv = _v[j];
          if (h[l][j] != rt_to[nv][j]) return 0;
          l += 1 << j;
        }
      return 1;
    };
    int l = 0, r = tot + 1;
    while (l + 1 != r) {
      int mid = (l + r) / 2;
      if (cmp_le(seg[mid]))
        l = mid;
      else
        r = mid;
    }
    int ans = -BIT::query(l);
    r = tot + 1;
    while (l + 1 != r) {
      int mid = (l + r) / 2;
      if (cmp_eq(seg[mid]))
        l = mid;
      else
        r = mid;
    }
    return ans + BIT::query(l);
  }
  int main() {
    pow_W[0] = 1;
    for (int i = 1; i < N; ++i) pow_W[i] = pow_W[i - 1] * W % D;
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i < n; ++i) {
      int u, v;
      static char c[10];
      scanf("%d%d%s", &u, &v, c);
      lk[u].push_back({v, *c});
      lk[v].push_back({u, *c});
    }
    dfs(1, 0);
    for (int i = 1; i <= m; ++i) {
      int t = dy_r[i - 1] + 2;
      scanf("%s", s + t);
      dy_r[i] = t + strlen(s + t) - 1;
      for (int j = t; j <= dy_r[i]; ++j) nex_r[j] = dy_r[i];
      for (int j = dy_r[i]; j >= t; --j) {
        h[j][0] = s[j];
        for (int k = 1; k < L; ++k) {
          if (j + (1 << k) - 1 <= dy_r[i])
            h[j][k] =
                (h[j][k - 1] * pow_W[1 << (k - 1)] + h[j + (1 << k - 1)][k - 1]) %
                D;
          else
            h[j][k] = -1;
        }
      }
    }
    SA::get_sa(dy_r[m]);
    tot = 0;
    static int np[N];
    for (int i = 1; i <= dy_r[m]; ++i) {
      int j = SA::sa[i];
      if (nex_r[j]) seg[np[j] = ++tot] = {j, nex_r[j]};
    }
    for (int i = 1; i <= q; ++i) {
      int u, v, l, r;
      scanf("%d%d%d%d", &u, &v, &l, &r);
      qu[i] = u;
      qv[i] = v;
      lkq[l - 1].push_back({i, -1});
      lkq[r].push_back({i, 1});
    }
    for (int i = 1; i <= m; ++i) {
      for (int j = dy_r[i - 1] + 2; j <= dy_r[i]; ++j) {
        BIT::add(np[j]);
      }
      for (auto pr : lkq[i]) {
        int j, w;
        tie(j, w) = pr;
        ans[j] += query(qu[j], qv[j]) * w;
      }
    }
    for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
  }
  