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 = 1e5 + 5, B = 150;
  int n, m, q, i, u, v, l, r;
  char c, fc[N];
  string s[N];
  struct tree {
    vector<pair<int, char>> e[N];
    int dad[N], dcnt, sz[N], ma[N], top[N], dep[N], dfn[N], be[N], en[N];
    void dfs1(int x, int fa) {
      dad[x] = fa;
      sz[x] = 1;
      dep[x] = dep[fa] + 1;
      for (auto u : e[x]) {
        int y = u.first;
        if (y == fa) continue;
        fc[y] = u.second;
        dfs1(y, x);
        sz[x] += sz[y];
        if (sz[y] > sz[ma[x]]) ma[x] = y;
      }
    }
    void dfs2(int x, int fa) {
      dfn[be[x] = ++dcnt] = x;
      if (ma[x]) top[ma[x]] = top[x], dfs2(ma[x], x);
      for (auto u : e[x]) {
        int y = u.first;
        if (y == fa || y == ma[x]) continue;
        top[y] = y;
        dfs2(y, x);
      }
      en[x] = dcnt;
    }
    inline vector<pair<int, int>> getpath(int u, int v) {
      vector<pair<int, int>> A, B;
      int x, y;
      for (; x = top[u], y = top[v], x != y;) {
        if (dep[x] > dep[y])
          A.push_back({be[u], be[x]}), u = dad[x];
        else
          B.push_back({be[y], be[v]}), v = dad[y];
      }
      A.push_back({be[u], be[v]});
      reverse(B.begin(), B.end());
      A.insert(A.end(), B.begin(), B.end());
      return A;
    }
    pair<int, int> pos[B + 5][N];
    int bo[N];
    void dfs3(int x, int fa, pair<int, int>* aa);
    inline void init();
  } T;
  struct node {
    int l, r, s;
  } t[N * 20];
  int tcnt;
  void ins(int x, int& y, int l, int r, int k) {
    t[y = ++tcnt] = t[x];
    ++t[y].s;
    if (l == r) return;
    int m = l + r >> 1;
    if (k <= m)
      ins(t[x].l, t[y].l, l, m, k);
    else
      ins(t[x].r, t[y].r, m + 1, r, k);
  }
  int ask(int x, int y, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return t[y].s - t[x].s;
    int m = l + r >> 1, ass = 0;
    if (ql <= m) ass += ask(t[x].l, t[y].l, l, m, ql, qr);
    if (m < qr) ass += ask(t[x].r, t[y].r, m + 1, r, ql, qr);
    return ass;
  }
  int cnt3;
  struct SAM {
    static const int M = N * 2;
    int ch[M][26], pre[M], step[M], xb;
    int be[M], en[M], dcnt, rt[M];
    vector<int> col[M], e[M];
    int ch2[M][26];
    SAM() {
      xb = 1;
      memset(ch[1], 0, 104);
    }
    char* ee[M];
    inline void build(string& s, int id) {
      int p, q, np, nq, lst = 1, i, x;
      reverse(s.begin(), s.end());
      for (i = 0; i < s.size(); ++i) {
        x = s[i] - 'a';
        p = lst;
        if (ch[p][x]) {
          q = ch[p][x];
          if (step[p] + 1 != step[q]) {
            step[nq = ++xb] = step[p] + 1;
            col[nq].push_back(id);
            lst = nq;
            ee[nq] = ee[q];
            memcpy(ch[nq], ch[q], 104);
            ee[q] -= step[nq] - step[pre[q]];
            pre[nq] = pre[q];
            pre[q] = nq;
            for (; p && ch[p][x] == q; p = pre[p]) ch[p][x] = nq;
          } else
            col[q].push_back(id), lst = q;
          continue;
        }
        step[np = ++xb] = step[p] + 1;
        col[np].push_back(id);
        memset(ch[np], 0, 104);
        for (; p && !ch[p][x]; p = pre[p]) ch[p][x] = np;
        if (p) {
          q = ch[p][x];
          if (step[p] + 1 != step[q]) {
            step[nq = ++xb] = step[p] + 1;
            ee[nq] = ee[q];
            memcpy(ch[nq], ch[q], 104);
            ee[q] -= step[nq] - step[pre[q]];
            pre[nq] = pre[q];
            pre[q] = pre[np] = nq;
            for (; p && ch[p][x] == q; p = pre[p]) ch[p][x] = nq;
          } else
            pre[np] = q;
        } else
          pre[np] = 1;
        ee[np] = &s[step[np] - step[pre[np]] - 1];
        lst = np;
      }
    }
    void dfs(int x) {
      be[x] = ++dcnt;
      rt[dcnt] = rt[dcnt - 1];
      for (int u : col[x]) ins(rt[dcnt], rt[dcnt], 1, m, u);
      for (int y : e[x]) ch2[x][*ee[y] - 'a'] = y;
      for (int i = 0; i < 26; ++i)
        if (ch2[x][i]) {
          dfs(ch2[x][i]);
        }
      en[x] = dcnt;
    }
    inline void init() {
      for (int i = 2; i <= xb; ++i) e[pre[i]].push_back(i);
      dfs(1);
    }
    inline void go1(pair<int, int>& u, int x) {
      int a, b;
      tie(a, b) = u;
      if (b != -1) {
        ++cnt3;
        if (ch[a][x])
          a = ch[a][x], ++b;
        else
          b = -1;
        u = {a, b};
      }
    }
    inline void go2(pair<int, int>& u, int x) {
      int a, b;
      tie(a, b) = u;
      if (b != -1) {
        if (b == step[a]) {
          a = ch2[a][x];
          ++b;
          if (!a) b = -1;
        } else {
          if (ee[a][-(b - step[pre[a]])] - 'a' != x)
            b = -1;
          else
            ++b;
        }
        u = {a, b};
      }
    }
  } S;
  void tree::dfs3(int x, int fa, pair<int, int>* aa) {
    for (auto uu : e[x]) {
      int y;
      char c;
      tie(y, c) = uu;
      if (y == fa) continue;
      aa[y] = aa[x];
      S.go1(aa[y], c - 'a');
      dfs3(y, x, aa);
    }
  }
  inline void tree::init() {
    dfs1(1, 0);
    top[1] = 1;
    dfs2(1, 0);
    static int pp[N];
    int i, j;
    mt19937 R(114514);
    for (i = 1; i <= n; ++i) pp[i] = i, swap(pp[i], pp[R() % i + 1]);
    for (i = 1; i <= min(n, B); ++i) {
      int x = pp[i], y;
      bo[be[x]] = i;
      pos[i][x] = {1, 0};
      for (; y = dad[x]; x = y)
        pos[i][y] = pos[i][x], S.go1(pos[i][y], fc[x] - 'a');
      for (j = 1; j <= n; ++j) {
        y = dfn[j];
        if (!pos[i][y].first)
          x = dad[y], pos[i][y] = pos[i][x], S.go1(pos[i][y], fc[y] - 'a');
      }
    }
  }
  inline int dir(const pair<int, int>& u) {
    int x, y;
    tie(x, y) = u;
    return x < y ? 1 : -1;
  }
  int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for (i = 1; i < n; ++i)
      cin >> u >> v >> c, T.e[u].push_back({v, c}), T.e[v].push_back({u, c});
    for (i = 1; i <= m; ++i) cin >> s[i], S.build(s[i], i);
    S.init();
    T.init();
    int cnt1 = 0, cnt2 = 0;
    for (; q--;) {
      cin >> u >> v >> l >> r;
      auto ve = T.getpath(u, v);
      int i, j;
      for (i = ve.size() - 1, j = ve[i].second;;) {
        if (T.bo[j] || j == T.be[u]) break;
        ++cnt1;
        if (j == ve[i].first)
          j = ve[--i].second;
        else
          j -= dir(ve[i]);
      }
      pair<int, int> a = j == T.be[u] ? pair<int, int>{1, 0} : T.pos[T.bo[j]][u];
      if (a.second == -1) {
        cout << '0' << '\n';
        continue;
      }
      for (; i + 1 < ve.size() || j != ve[i].second;) {
        int nj = j == ve[i].second ? ve[i + 1].first : j + dir(ve[i]),
            x = T.dfn[j], y = T.dfn[nj];
        ++cnt2;
        S.go2(a, (x == T.dad[y] ? fc[y] : fc[x]) - 'a');
        if (j == ve[i].second) ++i;
        j = nj;
      }
      tie(u, v) = a;
      cout << (v == -1 ? 0 : ask(S.rt[S.be[u] - 1], S.rt[S.en[u]], 1, m, l, r))
           << '\n';
    }
  }
  