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>
  const int HashMod = 981173233;
  const int HashBase = 114514;
  inline int qPow(int b, int e) {
    int a = 1;
    for (; e; e >>= 1, b = (int)((long long)b * b % HashMod))
      if (e & 1) a = (int)((long long)a * b % HashMod);
    return a;
  }
  inline int gInv(int b) { return qPow(b, HashMod - 2); }
  const int MLEN = 400005;
  int arr_pws[MLEN * 2], *pws = arr_pws + MLEN;
  void InitPws(int len) {
    pws[0] = 1;
    int invBase = gInv(HashBase);
    for (int i = 1; i <= len; ++i)
      pws[i] = (int)((long long)pws[i - 1] * HashBase % HashMod),
      pws[-i] = (int)((long long)pws[1 - i] * invBase % HashMod);
  }
  struct hsh {
    int len, val;
    hsh() : len(0), val(0) {}
    hsh(int x) : len(1), val(x) {}
    hsh(int l, int v) : len(l), val(v) {}
    friend hsh operator+(const hsh &p, const hsh &q) {
      return hsh(p.len + q.len,
                 (int)(((long long)p.val * pws[q.len] + q.val) % HashMod));
    }
    friend hsh operator-(const hsh &p, const hsh &q) {
      return hsh(p.len - q.len, (int)((long long)(p.val - q.val + HashMod) *
                                      pws[-q.len] % HashMod));
    }
    friend hsh operator/(const hsh &p, const hsh &q) {
      return hsh(p.len - q.len, (int)((p.val + (long long)(HashMod - q.val) *
                                                   pws[p.len - q.len]) %
                                      HashMod));
    }
    friend bool operator==(const hsh &p, const hsh &q) {
      return p.val == q.val && p.len == q.len;
    }
  };
  int totlen;
  char str[MLEN];
  hsh vv[MLEN];
  int bel[MLEN];
  inline hsh interval(int lb, int rb) { return vv[rb] / vv[lb - 1]; }
  struct SuffixArray {
    int N, Str[MLEN], SA[MLEN], rk[MLEN], SA2[MLEN];
    int Sig, Buk[MLEN], Tmp[MLEN];
    int Height[MLEN];
    inline void RSort() {
      for (int i = 1; i <= Sig; ++i) Buk[i] = 0;
      for (int i = 1; i <= N; ++i) ++Buk[rk[i]];
      for (int i = 1; i <= Sig; ++i) Buk[i] += Buk[i - 1];
      for (int i = N; i >= 1; --i) SA[Buk[rk[SA2[i]]]--] = SA2[i];
    }
    inline void BuildSA() {
      for (int i = 1; i <= N; ++i) rk[i] = Str[i], SA2[i] = i;
      rk[N + 1] = 0;
      Sig = 27, RSort();
      for (int j = 1; j < N; j <<= 1) {
        int P = 0;
        for (int i = 1; i <= j; ++i) SA2[++P] = N - j + i;
        for (int i = 1; i <= N; ++i)
          if (SA[i] > j) SA2[++P] = SA[i] - j;
        RSort();
        Tmp[SA[1]] = P = 1;
        for (int i = 2; i <= N; ++i) {
          if (rk[SA[i]] != rk[SA[i - 1]] || rk[SA[i] + j] != rk[SA[i - 1] + j])
            ++P;
          Tmp[SA[i]] = P;
        }
        for (int i = 1; i <= N; ++i) rk[i] = Tmp[i];
        Sig = P;
        if (Sig == N) break;
      }
    }
    inline void GetHeight() {
      int k = 0;
      for (int i = 1; i <= N; ++i) {
        if (rk[i] == 1)
          k = Height[1] = 0;
        else {
          if (k) --k;
          int j = SA[rk[i] - 1];
          while (i + k <= N && j + k <= N && Str[i + k] == Str[j + k]) ++k;
          Height[rk[i]] = k;
        }
      }
    }
    int BLCP[20][MLEN];
    inline void InitST() {
      for (int i = 1; i <= N; ++i) BLCP[0][i] = Height[i];
      for (int j = 0; 2 << j <= N; ++j)
        for (int i = 2 << j; i <= N; ++i)
          BLCP[j + 1][i] = std::min(BLCP[j][i], BLCP[j][i - (1 << j)]);
    }
    inline int LCP(int x, int y) {
      if (x == y) return N + 1;
      x = rk[x], y = rk[y];
      if (x > y) std::swap(x, y);
      int j = 31 - __builtin_clz(y - x);
      return std::min(BLCP[j][y], BLCP[j][x + (1 << j)]);
    }
    inline void GetRange(int pos, int k, int &lb, int &rb) {
      int lj = 0;
      while (pos > 1 << lj && BLCP[lj][pos] >= k) ++lj;
      for (--lj, lb = pos; lj >= 0; --lj)
        if (lb > 1 << lj && BLCP[lj][lb] >= k) lb -= 1 << lj;
      int rj = 0;
      while (N - pos >= 1 << rj && BLCP[rj][pos + (1 << rj)] >= k) ++rj;
      for (--rj, rb = pos; rj >= 0; --rj)
        if (N - rb >= 1 << rj && BLCP[rj][rb + (1 << rj)] >= k) rb += 1 << rj;
    }
  } SA;
  const int MN = 200005;
  int N;
  struct edg {
    int v, w;
  };
  std::vector<edg> G[MN];
  inline void AddEdge(int u, int v, int c) {
    G[u].push_back(edg{v, c});
    G[v].push_back(edg{u, c});
  }
  int dep[MN], par[19][MN], wgh[MN];
  hsh up[MN], dn[MN];
  int hit[MN], pref[MN];
  void DFS(int u, int p) {
    dep[u] = dep[par[0][u] = p] + 1;
    for (int j = 0; 2 << j < dep[u]; ++j) par[j + 1][u] = par[j][par[j][u]];
    hit[u] = 1;
    for (edg &e : G[u])
      if (e.v != p) {
        wgh[e.v] = e.w;
        up[e.v] = e.w + up[u];
        dn[e.v] = dn[u] + e.w;
        DFS(e.v, u);
        hit[u] = std::max(hit[u], hit[e.v] + 1);
        if (hit[pref[u]] < hit[e.v]) pref[u] = e.v;
      }
  }
  inline int LCA(int x, int y) {
    if (dep[x] < dep[y]) std::swap(x, y);
    for (int d = dep[x] - dep[y], j = 0; d; d >>= 1, ++j)
      if (d & 1) x = par[j][x];
    if (x == y) return x;
    for (int j = 18; j >= 0; --j)
      if (par[j][x] != par[j][y]) x = par[j][x], y = par[j][y];
    return par[0][x];
  }
  int top[MN], dfn[MN], idf[MN], dfc;
  std::vector<int> chain[MN];
  void DFS2(int u, int t) {
    top[u] = t;
    idf[dfn[u] = ++dfc] = u;
    if (u == t) {
      for (int i = 0, x = u; i <= hit[u]; ++i, x = par[0][x])
        chain[u].push_back(x);
    }
    if (pref[u]) DFS2(pref[u], t);
    for (edg &e : G[u])
      if (e.v != par[0][u] && e.v != pref[u]) DFS2(e.v, e.v);
  }
  inline int kpar(int x, int k) {
    if (!k) return x;
    int j = 31 - __builtin_clz(k);
    x = par[j][x], k -= 1 << j;
    k -= dep[x] - dep[top[x]];
    return k >= 0 ? chain[top[x]][k] : idf[dfn[top[x]] - k];
  }
  inline int kthchar(int x, int y, int lca, int k) {
    if (k <= dep[x] - dep[lca]) return wgh[kpar(x, k - 1)];
    return wgh[kpar(y, dep[x] + dep[y] - 2 * dep[lca] - k)];
  }
  inline hsh extract(int x, int y, int lca, int k) {
    if (k <= dep[x] - dep[lca]) return up[x] - up[kpar(x, k)];
    return (up[x] - up[lca]) +
           (dn[kpar(y, dep[x] + dep[y] - 2 * dep[lca] - k)] / dn[lca]);
  }
  const int MM = 200005;
  int M, bit[MM];
  inline void Add(int i) {
    for (; i <= M; i += i & -i) ++bit[i];
  }
  inline int Qur(int i) {
    int s = 0;
    for (; i; i -= i & -i) s += bit[i];
    return s;
  }
  const int MQ = 200005;
  int qL[MQ], qR[MQ], Ans[MQ];
  std::vector<int> qG[MLEN];
  int main() {
    int Q;
    InitPws(400000);
    scanf("%d%d%d", &N, &M, &Q);
    for (int i = 1; i <= N - 1; ++i) {
      int x, y;
      scanf("%d%d%s", &x, &y, str);
      AddEdge(x, y, str[0] - 'a' + 1);
    }
    DFS(1, 0);
    DFS2(1, 1);
    for (int i = 1; i <= M; ++i) {
      char *s = str + totlen;
      scanf("%s", s + 1);
      int len = (int)std::strlen(s + 1);
      for (int j = 1; j <= len; ++j)
        SA.Str[totlen + j] = s[j] - 'a' + 1, bel[totlen + j] = i;
      totlen += len;
      if (i != M) SA.Str[++totlen] = 27, str[totlen] = '{';
    }
    for (int i = 1; i <= totlen; ++i) vv[i] = vv[i - 1] + SA.Str[i];
    SA.N = totlen, SA.BuildSA(), SA.GetHeight(), SA.InitST();
    for (int q = 1; q <= Q; ++q) {
      int x, y, lca, len;
      scanf("%d%d%d%d", &x, &y, &qL[q], &qR[q]);
      lca = LCA(x, y);
      len = dep[x] + dep[y] - 2 * dep[lca];
      int lb = 1, rb = totlen - (M - 1), ans = -1;
      while (lb <= rb) {
        int mid = (lb + rb) / 2;
        int pos = SA.SA[mid];
        int lb2 = 1, rb2 = len, ans2 = 0;
        while (lb2 <= rb2) {
          int mid2 = (lb2 + rb2) / 2;
          if (extract(x, y, lca, mid2) == interval(pos, pos + mid2 - 1))
            ans2 = mid2, lb2 = mid2 + 1;
          else
            rb2 = mid2 - 1;
        }
        if (ans2 == len) {
          ans = mid;
          break;
        }
        if (kthchar(x, y, lca, ans2 + 1) < SA.Str[pos + ans2])
          rb = mid - 1;
        else
          lb = mid + 1;
      }
      if (ans == -1) {
        Ans[q] = 0;
        continue;
      }
      int l, r;
      SA.GetRange(ans, len, l, r);
      qG[r].push_back(q);
      qG[l - 1].push_back(-q);
    }
    for (int i = 1; i <= totlen - (M - 1); ++i) {
      Add(bel[SA.SA[i]]);
      for (int tq : qG[i]) {
        int o = tq < 0 ? -1 : 1;
        int q = o * tq;
        int sum = Qur(qR[q]) - Qur(qL[q] - 1);
        Ans[q] += o * sum;
      }
    }
    for (int q = 1; q <= Q; ++q) printf("%d\n", Ans[q]);
    return 0;
  }
  