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 P = 998244853;
  struct Z {
    int x;
    Z(int _x = 0) : x(_x) {}
    inline Z operator-() const {
      if (!x) return 0;
      return Z(P - x);
    }
    inline bool operator==(const Z &rhs) const { return x == rhs.x; }
    inline bool operator!=(const Z &rhs) const { return x != rhs.x; }
    inline Z &operator+=(const Z &rhs) {
      x += rhs.x;
      if (x >= P) x -= P;
      return *this;
    }
    inline Z &operator-=(const Z &rhs) {
      x -= rhs.x;
      if (x < 0) x += P;
      return *this;
    }
    inline Z &operator*=(const Z &rhs) {
      x = 1ull * x * rhs.x % P;
      return *this;
    }
    inline Z operator+(const Z &rhs) const {
      Z res = *this;
      return res += rhs;
    }
    inline Z operator-(const Z &rhs) const {
      Z res = *this;
      return res -= rhs;
    }
    inline Z operator*(const Z &rhs) const {
      Z res = *this;
      return res *= rhs;
    }
  };
  Z pw[18];
  int n, m, q, l;
  vector<pair<int, int>> g[100005];
  int bel[200005];
  char s[200005];
  using PI = pair<int, int>;
  using PII = pair<PI, int>;
  PII x[200005], y[200005];
  int buc[200005], sa[200005], rk[200005];
  vector<PII> qry[200005];
  int ans[100005];
  int dep[100005], par[100005][18];
  Z f[200005][18], f1[100005][18], f2[100005][18];
  void dfs(int u, int fa) {
    for (const auto &p : g[u]) {
      int v = p.first, w = p.second;
      if (v == fa) continue;
      dep[v] = dep[u] + 1;
      par[v][0] = u;
      f1[v][0] = f2[v][0] = w;
      for (int k = 1; k < 18; ++k) {
        par[v][k] = par[par[v][k - 1]][k - 1];
        f1[v][k] = f1[v][k - 1] + pw[k - 1] * f1[par[v][k - 1]][k - 1];
        f2[v][k] = pw[k - 1] * f2[v][k - 1] + f2[par[v][k - 1]][k - 1];
      }
      dfs(v, u);
    }
  }
  int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int k = 17; ~k; --k)
      if (dep[par[u][k]] >= dep[v]) u = par[u][k];
    if (u == v) return u;
    for (int k = 17; ~k; --k) {
      if (par[u][k] != par[v][k]) {
        u = par[u][k];
        v = par[v][k];
      }
    }
    return par[u][0];
  }
  namespace BIT {
  int c[100005];
  inline void add(int p) {
    if (!p) return;
    for (; p <= m; p += p & -p) ++c[p];
  }
  inline int query(int p) {
    int res = 0;
    for (; p; p -= p & -p) res += c[p];
    return res;
  }
  inline int query(int l, int r) { return query(r) - query(l - 1); }
  }  // namespace BIT
  inline int cmp(int pos, int u, int v, int w) {
    int l1 = dep[u] - dep[w], l2 = dep[v] - dep[w];
    Z x = 0, y = 0, coef = 1;
    while (l1) {
      int k = __builtin_ctz(l1);
      Z x1 = x + coef * f1[u][k];
      Z y1 = y + coef * f[pos][k];
      if (x1 != y1) {
        for (int i = k - 1; ~i; --i) {
          Z x2 = x + coef * f1[u][i];
          Z y2 = y + coef * f[pos][i];
          if (x2 == y2) {
            x = x2, y = y2;
            u = par[u][i];
            pos += 1 << i;
            coef *= pw[i];
          }
        }
        return f[pos][0].x > f1[u][0].x ? 1 : -1;
      } else {
        x = x1, y = y1;
        u = par[u][k];
        pos += 1 << k;
        coef *= pw[k];
      }
      l1 -= 1 << k;
    }
    vector<int> ver;
    while (l2) {
      ver.emplace_back(v);
      int k = __builtin_ctz(l2);
      v = par[v][k];
      l2 -= 1 << k;
    }
    reverse(ver.begin(), ver.end());
    for (auto v : ver) {
      int k = __builtin_ctz(dep[v] - dep[u]);
      Z x1 = x + coef * f2[v][k];
      Z y1 = y + coef * f[pos][k];
      if (x1 != y1) {
        int cur = v;
        for (int i = k - 1; ~i; --i) {
          Z x2 = x + coef * f2[par[cur][i]][i];
          Z y2 = y + coef * f[pos][i];
          if (x2 != y2) {
            cur = par[cur][i];
          } else {
            x = x2, y = y2;
            pos += 1 << i;
            coef *= pw[i];
          }
        }
        return f[pos][0].x > f2[cur][0].x ? 1 : -1;
      } else {
        x = x1, y = y1;
        u = v;
        pos += 1 << k;
        coef *= pw[k];
      }
    }
    return 0;
  }
  int main() {
    pw[0] = 2333;
    for (int i = 1; i < 18; ++i) pw[i] = pw[i - 1] * pw[i - 1];
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i < n; ++i) {
      int u, v;
      scanf("%d%d", &u, &v);
      char c = getchar();
      while (!isalpha(c)) c = getchar();
      g[u].emplace_back(v, c);
      g[v].emplace_back(u, c);
    }
    for (int i = 1; i <= m; ++i) {
      scanf("%s", s + l + 1);
      int len = strlen(s + l + 1);
      fill(bel + l + 1, bel + l + len + 1, i);
      l += len;
      s[++l] = '@';
    }
    for (int i = 1; i <= l; ++i) rk[i] = s[i];
    int tot = l;
    for (int k = 1; k < l; k <<= 1) {
      for (int i = 1; i <= l; ++i)
        x[i] = PII(PI(rk[i], i + k > l ? 0 : rk[i + k]), i);
      if (k == 1) {
        sort(x + 1, x + l + 1);
      } else {
        memset(buc + 1, 0, tot * 4);
        for (int i = 1; i <= l; ++i) ++buc[x[i].first.second];
        for (int i = 1; i <= tot; ++i) buc[i] += buc[i - 1];
        for (int i = 1; i <= l; ++i) y[buc[x[i].first.second]--] = x[i];
        memset(buc + 1, 0, tot * 4);
        for (int i = 1; i <= l; ++i) ++buc[y[i].first.first];
        for (int i = 1; i <= tot; ++i) buc[i] += buc[i - 1];
        for (int i = l; i; --i) x[buc[y[i].first.first]--] = y[i];
      }
      tot = 0;
      for (int i = 1; i <= l; ++i) {
        if (i == 1 || x[i].first != x[i - 1].first) ++tot;
        rk[x[i].second] = tot;
      }
      if (tot == l) break;
    }
    for (int i = 1; i <= l; ++i) sa[rk[i]] = i;
    for (int i = l; i; --i) {
      f[i][0] = s[i];
      for (int k = 1; i + (1 << k) - 1 <= l; ++k)
        f[i][k] = f[i][k - 1] + pw[k - 1] * f[i + (1 << (k - 1))][k - 1];
    }
    dfs(1, 0);
    for (int i = 1; i <= q; ++i) {
      int u, v, L, R;
      scanf("%d%d%d%d", &u, &v, &L, &R);
      int w = LCA(u, v);
      int l = 1, r = ::l, pos = ::l + 1;
      while (l <= r) {
        int mid = (l + r) >> 1;
        if (cmp(sa[mid], u, v, w) > 0)
          pos = mid, r = mid - 1;
        else
          l = mid + 1;
      }
      l = 1, r = pos - 1;
      int pos1 = pos;
      while (l <= r) {
        int mid = (l + r) >> 1;
        if (cmp(sa[mid], u, v, w) == 0)
          pos1 = mid, r = mid - 1;
        else
          l = mid + 1;
      }
      if (pos1 != pos) {
        qry[pos1 - 1].push_back(PII(PI(L, R), -i));
        qry[pos - 1].push_back(PII(PI(L, R), i));
      }
    }
    for (int i = 1; i <= l; ++i) {
      BIT::add(bel[sa[i]]);
      for (const auto &p : qry[i]) {
        int l, r, id = p.second;
        tie(l, r) = p.first;
        if (id < 0)
          ans[-id] -= BIT::query(l, r);
        else
          ans[id] += BIT::query(l, r);
      }
    }
    for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
    return 0;
  }
  