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 = 1e6 + 5;
  int n, m, q, tot, v1[N], v2[N], sa[N], rk[N], hgt[N], f[N][19], c[N], lg[N],
      ans[N], tr[N];
  int fa[N], son[N], dfn[N], top[N], idx, idf[N], siz[N], dep[N], seq[N], id[N];
  char str[N], s[N], vl[N];
  vector<pair<int, int>> g[N], up, dn;
  struct Q {
    int l, r, id;
  };
  vector<Q> qr[N];
  void modify(int x, int k) {
    for (; x <= m; x += x & -x) tr[x] += k;
  }
  int query(int x) {
    int ret = 0;
    for (; x; x -= x & -x) ret += tr[x];
    return ret;
  }
  void build() {
    for (int i = 1; i <= tot; i++) v1[i] = s[i] - 'a' + 1, ++c[v1[i]];
    for (int i = 2; i <= 27; i++) c[i] += c[i - 1];
    for (int i = 1; i <= tot; i++) sa[c[v1[i]]--] = i;
    for (int k = 1; k <= tot; k <<= 1) {
      int cnt = 0;
      memset(c, 0, sizeof(c));
      for (int i = tot - k + 1; i <= tot; i++) v2[++cnt] = i;
      for (int i = 1; i <= tot; i++)
        if (sa[i] > k) v2[++cnt] = sa[i] - k;
      for (int i = 1; i <= tot; i++) c[v1[i]]++;
      for (int i = 1; i <= tot; i++) c[i] += c[i - 1];
      for (int i = tot; i >= 1; i--) {
        sa[c[v1[v2[i]]]--] = v2[i];
        v2[i] = 0;
      }
      swap(v1, v2);
      cnt = 1;
      v1[sa[1]] = 1;
      for (int i = 2; i <= tot; i++) {
        if (v2[sa[i]] == v2[sa[i - 1]] && v2[sa[i] + k] == v2[sa[i - 1] + k])
          v1[sa[i]] = cnt;
        else
          v1[sa[i]] = ++cnt;
      }
    }
    for (int i = 1; i <= tot; i++) rk[sa[i]] = i;
    for (int i = 1, j = 0; i <= tot; i++) {
      if (j) --j;
      while (s[i + j] == s[sa[rk[i] - 1] + j]) j++;
      hgt[rk[i]] = j;
    }
    for (int i = 1; i <= tot; i++) f[i][0] = hgt[i];
    for (int j = 1; j <= 18; j++)
      for (int i = 1; i + (1 << j) - 1 <= tot; i++)
        f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
    for (int i = 2; i <= tot; i++) lg[i] = lg[i >> 1] + 1;
  }
  int lcp(int x, int y) {
    int l = rk[x], r = rk[y];
    if (l == r) return tot - x + 1;
    if (l > r) swap(l, r);
    ++l;
    int k = lg[r - l + 1];
    return min(f[l][k], f[r - (1 << k) + 1][k]);
  }
  void dfs1(int u) {
    siz[u] = 1;
    for (auto [v, w] : g[u]) {
      if (v == fa[u]) continue;
      fa[v] = u;
      dep[v] = dep[u] + 1;
      vl[v] = w;
      dfs1(v);
      siz[u] += siz[v];
      if (siz[v] > siz[son[u]]) son[u] = v;
    }
  }
  void dfs2(int u, int tf) {
    dfn[u] = ++idx;
    seq[idx] = u;
    s[++tot] = vl[u];
    top[u] = tf;
    if (son[u]) dfs2(son[u], tf);
    for (auto [v, w] : g[u]) {
      if (v == fa[u] || v == son[u]) continue;
      dfs2(v, v);
    }
  }
  int getl() {
    auto check = [&](int x) {
      for (auto [l, r] : up) {
        int lp = lcp(x, l);
        if (lp < r - l + 1) return s[x + lp] < s[l + lp];
        x += r - l + 1;
      }
      return false;
    };
    int l = 0, r = tot;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(sa[mid]))
        l = mid;
      else
        r = mid - 1;
    }
    return l + 1;
  }
  int getr() {
    auto check = [&](int x) {
      for (auto [l, r] : up) {
        int lp = lcp(x, l);
        if (lp < r - l + 1) return s[x + lp] > s[l + lp];
        x += r - l + 1;
      }
      return false;
    };
    int l = 1, r = tot + 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (check(sa[mid]))
        r = mid;
      else
        l = mid + 1;
    }
    return l - 1;
  }
  int main() {
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i < n; i++) {
      int u, v;
      char w;
      scanf("%d %d %c", &u, &v, &w);
      g[u].push_back({v, w});
      g[v].push_back({u, w});
    }
    vl[1] = 'a';
    dfs1(1);
    dfs2(1, 0);
    for (int i = n; i >= 1; i--) {
      idf[seq[i]] = ++tot;
      s[tot] = vl[seq[i]];
    }
    for (int i = 1; i <= m; i++) {
      scanf("%s", str + 1);
      s[++tot] = 'z' + 1;
      int l = strlen(str + 1);
      for (int j = 1; j <= l; j++) s[++tot] = str[j], id[tot] = i;
    }
    build();
    for (int i = 1; i <= q; i++) {
      dn.clear();
      up.clear();
      int u, v, l, r;
      scanf("%d%d%d%d", &u, &v, &l, &r);
      while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) {
          dn.push_back({dfn[top[v]], dfn[v]});
          v = fa[top[v]];
        } else {
          up.push_back({idf[u], idf[top[u]]});
          u = fa[top[u]];
        }
      }
      if (dep[u] > dep[v])
        up.push_back({idf[u], idf[v] - 1});
      else if (dep[u] < dep[v])
        dn.push_back({dfn[u] + 1, dfn[v]});
      reverse(dn.begin(), dn.end());
      for (auto p : dn) up.push_back(p);
      int L = getl(), R = getr();
      if (L <= R) {
        qr[L - 1].push_back((Q){l, r, -i});
        qr[R].push_back((Q){l, r, i});
      }
    }
    for (int i = 1; i <= tot; i++) {
      if (id[sa[i]]) modify(id[sa[i]], 1);
      for (auto [l, r, id] : qr[i]) {
        int res = query(r) - query(l - 1);
        if (id < 0)
          ans[-id] -= res;
        else
          ans[id] += res;
      }
    }
    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
    return 0;
  }
  