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>
  template <typename _Tp>
  void read(_Tp &x) {
    char ch(getchar());
    bool f(false);
    while (!isdigit(ch)) f |= ch == 45, ch = getchar();
    x = ch & 15, ch = getchar();
    while (isdigit(ch)) x = x * 10 + (ch & 15), ch = getchar();
    if (f) x = -x;
  }
  template <typename _Tp, typename... Args>
  void read(_Tp &t, Args &...args) {
    read(t);
    read(args...);
  }
  const int N = 100005, M = N << 1, mod = 1000526981, base = 2333;
  template <typename _Tp1, typename _Tp2>
  inline void add(_Tp1 &a, _Tp2 b) {
    a = a + b >= mod ? a + b - mod : a + b;
  }
  template <typename _Tp1, typename _Tp2>
  inline void sub(_Tp1 &a, _Tp2 b) {
    a = a - b < 0 ? a - b + mod : a - b;
  }
  long long ksm(long long a, long long b = mod - 2) {
    long long res = 1;
    while (b) {
      if (b & 1) res = res * a % mod;
      a = a * a % mod, b >>= 1;
    }
    return res;
  }
  int ans[N], sa[M], rk[M], tax[M], tp[M], s[M], a[M], dp[M], p;
  char t[N];
  std::vector<std::pair<int, int> > e[N];
  void Rsort(int n, int m) {
    memset(tax, 0, (m + 3) << 2);
    for (int i = 1; i <= n; ++i) ++tax[rk[i]];
    for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
    for (int i = n; i >= 1; --i) sa[tax[rk[tp[i]]]--] = tp[i];
  }
  void SA(int n, int m) {
    for (int i = 1; i <= n; ++i) rk[i] = s[i], tp[i] = i;
    Rsort(n, m);
    for (int w = 1, p = 0; p < n; w <<= 1, m = p) {
      p = 0;
      for (int i = 0; i < w; ++i) tp[++p] = n - i;
      for (int i = 1; i <= n; ++i)
        if (sa[i] > w) tp[++p] = sa[i] - w;
      Rsort(n, m), memcpy(tp, rk, (n + 3) << 2), rk[sa[1]] = p = 1;
      for (int i = 2; i <= n; ++i)
        rk[sa[i]] =
            tp[sa[i - 1]] == tp[sa[i]] && tp[sa[i - 1] + w] == tp[sa[i] + w]
                ? p
                : ++p;
    }
  }
  int anc[N][18], f[N][18], g[N][18], pw[N], dep[N], ipw[N];
  void dfs(int x, int fa) {
    for (int i = 1; i < 18 && anc[x][i - 1]; ++i) {
      anc[x][i] = anc[anc[x][i - 1]][i - 1];
      f[x][i] =
          (1LL * pw[1 << (i - 1)] * f[x][i - 1] + f[anc[x][i - 1]][i - 1]) % mod;
      g[x][i] =
          (g[x][i - 1] + 1LL * pw[1 << (i - 1)] * g[anc[x][i - 1]][i - 1]) % mod;
    }
    for (auto [v, w] : e[x])
      if (v != fa)
        anc[v][0] = x, f[v][0] = w, g[v][0] = w, dep[v] = dep[x] + 1, dfs(v, x);
  }
  int lca(int x, int y) {
    if (dep[x] < dep[y]) std::swap(x, y);
    for (int i = 17; i >= 0; --i)
      if (dep[anc[x][i]] >= dep[y]) x = anc[x][i];
    if (x == y) return x;
    for (int i = 17; i >= 0; --i)
      if (anc[x][i] != anc[y][i]) x = anc[x][i], y = anc[y][i];
    return anc[x][0];
  }
  int jump(int x, int k) {
    for (int i = 17; i >= 0; --i)
      if (k >> i & 1) x = anc[x][i];
    return x;
  }
  int getf(int x, int k) {
    int ans = 0;
    for (int i = 17; i >= 0; --i)
      if (k >> i & 1)
        ans = (1LL * ans * pw[1 << i] + f[x][i]) % mod, x = anc[x][i];
    return ans;
  }
  int getg(int x, int k) {
    int ans = 0, coef = 1;
    for (int i = 17; i >= 0; --i)
      if (k >> i & 1)
        ans = (1LL * coef * g[x][i] + ans) % mod,
        coef = 1LL * coef * pw[1 << i] % mod, x = anc[x][i];
    return ans;
  }
  int x, y, z, d;
  int lcp(int pos) {
    int x = ::x, y = ::y, z = ::z;
    int len = std::min(dep[x] - dep[z], p - pos + 1);
    if ((dp[pos + len - 1] + 1LL * (mod - dp[pos - 1]) * pw[len]) % mod ==
        getf(x, len)) {
      pos += len, len = std::min(dep[y] - dep[z], p - pos + 1);
      y = jump(y, dep[y] - dep[z] - len);
      int cur = getg(y, len), rest = len;
      if ((dp[pos + len - 1] + 1LL * (mod - dp[pos - 1]) * pw[len]) % mod == cur)
        return d;
      for (int i = 17; i >= 0; --i)
        if ((1 << i) <= rest) {
          int tmp = 1LL * (cur - g[y][i] + mod) * ipw[1 << i] % mod,
              LEN = rest - (1 << i);
          if (tmp !=
              (dp[pos + LEN - 1] + 1LL * (mod - dp[pos - 1]) * pw[LEN]) % mod)
            cur = tmp, rest = LEN, y = anc[y][i];
        }
      return dep[x] - dep[z] + rest - 1;
    } else {
      int cur = 0, cl = 0;
      for (int i = 17; i >= 0; --i)
        if (cl + (1 << i) <= len) {
          int tmp = (1LL * cur * pw[1 << i] + f[x][i]) % mod, LEN = cl + (1 << i);
          if (tmp ==
              (dp[pos + LEN - 1] + 1LL * (mod - dp[pos - 1]) * pw[LEN]) % mod)
            cur = tmp, cl = LEN, x = anc[x][i];
        }
      return cl;
    }
  }
  int cmp(int pos) {
    int len = lcp(pos);
    if (len == d) return 1;
    int A = len + 1 <= dep[x] - dep[z] ? f[jump(x, len)][0]
                                       : f[jump(y, d - len - 1)][0],
        B = s[pos + len];
    return A < B;
  }
  bool check(int pos) {
    if (p - pos + 1 < d) return 0;
    int len = dep[x] - dep[z];
    if ((dp[pos + len - 1] + 1LL * (mod - dp[pos - 1]) * pw[len]) % mod ==
        getf(x, len)) {
      pos += len, len = dep[y] - dep[z];
      if ((dp[pos + len - 1] + 1LL * (mod - dp[pos - 1]) * pw[len]) % mod ==
          getg(y, len))
        return 1;
    }
    return 0;
  }
  int c[N];
  void add(int x, int C) {
    ++x;
    for (; x < N; x += ((x) & (-(x)))) c[x] += C;
  }
  int ask(int x) {
    ++x;
    int ans = 0;
    for (; x; x -= ((x) & (-(x)))) ans += c[x];
    return ans;
  }
  struct qry {
    int l, r, id, opt;
  };
  std::vector<qry> Q[M];
  int main() {
    pw[0] = 1;
    for (int i = 1; i < N; ++i) pw[i] = 1LL * base * pw[i - 1] % mod;
    long long inv = ksm(base);
    ipw[0] = 1;
    for (int i = 1; i < N; ++i) ipw[i] = 1LL * inv * ipw[i - 1] % mod;
    int n, m, q;
    read(n, m, q);
    char ch;
    for (int i = 1, x, y; i < n; ++i) {
      read(x, y);
      do {
        ch = getchar();
      } while (!isalpha(ch));
      e[x].push_back({y, ch}), e[y].push_back({x, ch});
    }
    for (int i = 1; i <= m; ++i) {
      scanf("%s", t + 1);
      int len = strlen(t + 1);
      for (int j = 1; j <= len; ++j) s[++p] = t[j], a[p] = i;
      s[++p] = i + 127, a[p] = 0;
    }
    for (int i = 1; i <= p; ++i) dp[i] = (1LL * dp[i - 1] * base + s[i]) % mod;
    SA(p, 128 + m);
    dep[1] = 1, dfs(1, 0);
    int L, R;
    for (int i = 1; i <= q; ++i) {
      read(x, y, L, R), z = lca(x, y), d = dep[x] + dep[y] - dep[z] * 2;
      int l = 1, r = p, mid;
      while (l < r) mid = (l + r) >> 1, cmp(sa[mid]) ? r = mid : l = mid + 1;
      int fir = l;
      l = fir - 1, r = p;
      while (l < r)
        mid = (l + r + 1) >> 1, check(sa[mid]) ? l = mid : r = mid - 1;
      Q[l].push_back({L, R, i, 1}), Q[fir - 1].push_back({L, R, i, -1});
    }
    for (int i = 1; i <= p; ++i) {
      add(a[sa[i]], 1);
      for (auto [l, r, id, opt] : Q[i]) ans[id] += opt * (ask(r) - ask(l - 1));
    }
    for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
    return 0;
  }
  