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;
  int fastPow(int base, int e, int mod) {
    int result = 1;
    base %= mod;
    while (e) {
      if (e & 1) result = (int)result * base % mod;
      base = (int)base * base % mod;
      e >>= 1;
    }
    return result;
  }
  int mod = 998244353, base = 47;
  struct Edge {
    int nex, to, len;
  } edge[200005];
  int n, m, q, x, y, z, l, r, ans, mi[200005];
  int E, head[200005], dep[200005], w[200005], fa[200005][17], fU[200005][17],
      fD[200005][17];
  int S[200005], posl[200005], posr[200005], a[200005], b[200005], c[200005],
      tot[200005], rk[200005 << 1], sa[200005], sum[200005];
  int V, rt[200005], ls[200005 * 20], rs[200005 * 20], f[200005 * 20];
  char s[200005];
  void add(int x, int y, int z) {
    edge[E] = Edge{head[x], y, z};
    head[x] = E++;
  }
  int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 16; i >= 0; i--)
      if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    if (x == y) return x;
    for (int i = 16; i >= 0; i--)
      if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
  }
  void dfs(int k, int f, int s, int lst) {
    dep[k] = s, w[k] = lst;
    fa[k][0] = f, fU[k][0] = fD[k][0] = lst;
    for (int i = 1; i < 17; i++) {
      fa[k][i] = fa[fa[k][i - 1]][i - 1];
      fU[k][i] =
          (fU[fa[k][i - 1]][i - 1] + (long long)mi[1 << i - 1] * fU[k][i - 1]) %
          mod;
      fD[k][i] =
          (fD[k][i - 1] + (long long)mi[1 << i - 1] * fD[fa[k][i - 1]][i - 1]) %
          mod;
    }
    for (int i = head[k]; i != -1; i = edge[i].nex)
      if (edge[i].to != f) dfs(edge[i].to, k, s + 1, edge[i].len);
  }
  int Hash(int x, int y) {
    return (sum[y] - (long long)mi[y - x + 1] * sum[x - 1] % mod + mod) % mod;
  }
  void build() {
    for (int i = 1; i <= n; i++)
      sum[i] = ((long long)base * sum[i - 1] + S[i]) % mod;
    int m = 27;
    for (int i = 1; i <= n; i++) rk[i] = S[i];
    for (int i = 1;; i <<= 1) {
      memset(tot, 0, sizeof(tot));
      for (int j = 1; j <= n; j++) tot[rk[j + i]]++;
      for (int j = 1; j <= m; j++) tot[j] += tot[j - 1];
      for (int j = n; j; j--) a[tot[rk[j + i]]--] = j;
      memset(tot, 0, sizeof(tot));
      for (int j = 1; j <= n; j++) tot[rk[j]]++;
      for (int j = 1; j <= m; j++) tot[j] += tot[j - 1];
      for (int j = n; j; j--) b[tot[rk[a[j]]]--] = a[j];
      m = 0;
      for (int j = 1; j <= n; j++) {
        if ((j == 1) || (rk[b[j]] != rk[b[j - 1]]) ||
            (rk[b[j] + i] != rk[b[j - 1] + i]))
          m++;
        c[b[j]] = m;
      }
      memcpy(rk, c, sizeof(c));
      if (m == n) break;
    }
    for (int i = 1; i <= n; i++) sa[rk[i]] = i;
  }
  int cmp(int l, int r) {
    int k = x;
    for (int i = 16; i >= 0; i--)
      if ((dep[fa[k][i]] >= dep[z]) && (l + (1 << i) - 1 <= r)) {
        if (fU[k][i] == Hash(l, l + (1 << i) - 1)) k = fa[k][i], l += (1 << i);
      }
    if (l > r) return ((k == z) && (y == z)) - 1;
    if (k != z) return ((w[k] < S[l]) << 1) - 1;
    vector<pair<int, int> > v;
    k = y;
    for (int i = 16; i >= 0; i--)
      if (dep[fa[k][i]] >= dep[z]) {
        v.push_back(make_pair(k, i));
        k = fa[k][i];
      }
    while (!v.empty()) {
      k = v.back().first;
      int i = v.back().second;
      if ((l + (1 << i) - 1 > r) || (fD[k][i] != Hash(l, l + (1 << i) - 1)))
        break;
      v.pop_back(), l += (1 << i);
    }
    if (v.empty()) return l <= r;
    k = v.back().first;
    for (int i = v.back().second - 1; i >= 0; i--)
      if ((l + (1 << i) - 1 <= r) &&
          (fD[fa[k][i]][i] == Hash(l, l + (1 << i) - 1)))
        l += (1 << i);
      else
        k = fa[k][i];
    if ((l > r) || (S[l] < w[k])) return -1;
    return 1;
  }
  int New(int k) {
    f[++V] = f[k], ls[V] = ls[k], rs[V] = rs[k];
    return V;
  }
  void update(int &k, int l, int r, int x) {
    k = New(k), f[k]++;
    if (l == r) return;
    int mid = (l + r >> 1);
    if (x <= mid)
      update(ls[k], l, mid, x);
    else
      update(rs[k], mid + 1, r, x);
  }
  int query(int k, int l, int r, int x, int y) {
    if ((!k) || (l > y) || (x > r)) return 0;
    if ((x <= l) && (r <= y)) return f[k];
    int mid = (l + r >> 1);
    return query(ls[k], l, mid, x, y) + query(rs[k], mid + 1, r, x, y);
  }
  signed main() {
    mi[0] = 1;
    for (int i = 1; i < 200005; i++) mi[i] = (long long)base * mi[i - 1] % mod;
    scanf("%d%d%d", &n, &m, &q);
    memset(head, -1, sizeof(head));
    for (int i = 1; i < n; i++) {
      scanf("%d%d%s", &x, &y, s);
      add(x, y, s[0] - 'a' + 1), add(y, x, s[0] - 'a' + 1);
    }
    dfs(1, 0, 1, 0);
    n = 0;
    for (int i = 1; i <= m; i++) {
      scanf("%s", s);
      posl[i] = n + 1;
      for (int j = 0; s[j]; j++) S[++n] = s[j] - 'a' + 1;
      posr[i] = n;
      if (i < m) S[++n] = 27;
    }
    build();
    for (int i = 1; i <= n; i++) {
      rt[i] = rt[i - 1];
      update(rt[i], 1, n, sa[i]);
    }
    for (int i = 1; i <= q; i++) {
      scanf("%d%d%d%d", &x, &y, &l, &r), z = lca(x, y);
      int d = dep[x] + dep[y] - (dep[z] << 1), L = posl[l], R = posr[r] - d + 1;
      if (cmp(sa[n], n) < 0) {
        printf("0\n");
        continue;
      }
      l = 1, r = n;
      while (l < r) {
        int mid = (l + r >> 1);
        if (cmp(sa[mid], n) >= 0)
          r = mid;
        else
          l = mid + 1;
      }
      r = n, ans = query(rt[l - 1], 1, n, L, R);
      if ((sa[l] + d - 1 > n) || (cmp(sa[l], sa[l] + d - 1))) {
        printf("0\n");
        continue;
      }
      while (l < r) {
        int mid = (l + r + 1 >> 1);
        if ((sa[mid] + d - 1 <= n) && (!cmp(sa[mid], sa[mid] + d - 1)))
          l = mid;
        else
          r = mid - 1;
      }
      ans = query(rt[l], 1, n, L, R) - ans;
      printf("%d\n", ans);
    }
    return 0;
  }
  