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>
  #pragma GCC optimize("Ofast")
  #pragma GCC optimize("unroll-loops")
  #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
  using std::cin;
  using std::cout;
  struct BS {
    static const int size = 200000 / 64 + 1;
    unsigned long long a[size];
    inline int count() const {
      int sum = 0;
      for (int i = 0; i != size; ++i) {
        sum += __builtin_popcountll(a[i]);
      }
      return sum;
    }
    inline bool test(int pos) const { return a[pos >> 6] >> (pos & 63) & 1; }
    inline void set(int pos) { a[pos >> 6] |= 1ull << (pos & 63); }
    inline void reset(int pos) { a[pos >> 6] &= ~(1ull << (pos & 63)); }
    inline BS& operator&=(const BS& x) {
      for (int i = 0; i != size; ++i) {
        a[i] &= x.a[i];
      }
      return *this;
    }
    inline BS& shift(const BS& A, int __shift, const BS& B) {
      const int __wshift = __shift / 64;
      const int __offset = __shift % 64;
      const int _Nw = size;
      const unsigned long long* _M_w = A.a;
      if (__offset == 0)
        for (int __n = _Nw - 1; __n >= __wshift; --__n)
          a[__n] = _M_w[__n - __wshift] & B.a[__n];
      else {
        const int __sub_offset = (64 - __offset);
        for (int __n = _Nw - 1; __n > __wshift; --__n)
          a[__n] = ((_M_w[__n - __wshift] << __offset) |
                    (_M_w[__n - __wshift - 1] >> __sub_offset)) &
                   B.a[__n];
        a[__wshift] = (_M_w[0] << __offset) & B.a[__wshift];
      }
      std::fill(a + 0, a + __wshift, 0ull);
      return *this;
    }
  };
  const int N = 200005;
  const int M = 400005;
  const int B = 400;
  struct SAM {
    char T[N];
    int c[M][27], mx[M], fa[M], right[M], la, tot;
    int n;
    inline void append(int w, int o) {
      int p = la, now = la = ++tot;
      mx[now] = mx[p] + 1, right[now] = o;
      for (; p && !c[p][w]; p = fa[p]) c[p][w] = now;
      if (!p)
        fa[now] = 1;
      else {
        int q = c[p][w];
        if (mx[q] == mx[p] + 1)
          fa[now] = q;
        else {
          int x = ++tot;
          mx[x] = mx[p] + 1;
          memcpy(c[x], c[q], sizeof(c[0]));
          fa[x] = fa[q], fa[q] = fa[now] = x;
          for (; p && c[p][w] == q; p = fa[p]) c[p][w] = x;
        }
      }
    }
    int head[M], next[M];
    inline void link(int fa, int x) { next[x] = head[fa], head[fa] = x; }
    int L[M], R[M], stack[N], cnt;
    struct qwq {
      int l, r;
      BS w;
      inline void move(int L, int R, SAM* A) {
        for (; l > L;) w.set(A->stack[--l]);
        for (; r < R;) w.set(A->stack[++r]);
        for (; l < L;) w.reset(A->stack[l++]);
        for (; r > R;) w.reset(A->stack[r--]);
      }
    };
    qwq* AWA[N / B + 1][N / B + 1];
    qwq mem[N / B * 4], *_ptr = mem;
    inline void dfs0(int x) {
      L[x] = cnt + 1;
      if (right[x]) stack[++cnt] = right[x];
      for (int i = head[x]; i; i = next[i]) {
        dfs0(i);
      }
      R[x] = cnt;
    }
    inline void rev() {
      for (int i = 1; i <= cnt; ++i) stack[i] = n + 1 - stack[i];
    }
    inline const BS& get(int l, int r) {
      AWA[l / B][r / B]->move(l, r, this);
      return AWA[l / B][r / B]->w;
    }
    inline const BS& get(int id) {
      static BS EP;
      if (id == 0) return EP;
      return get(L[id], R[id]);
    }
    inline void init() {
      la = tot = 1;
      for (int i = 1; i <= n; ++i) append(T[i] - 'a', i);
      for (int i = 2; i <= tot; ++i) {
        link(fa[i], i);
      }
      dfs0(1);
      for (int i = 1; i <= tot; ++i) {
        qwq*& ptr = AWA[L[i] / B][R[i] / B];
        if (ptr == nullptr) {
          ptr = _ptr++;
          ptr->l = L[i];
          ptr->r = L[i] - 1;
        }
      }
    }
  } rev, sam;
  int n, m, q;
  struct edge {
    int to, nxt, v;
  } e[N << 1];
  int h[N], num;
  inline void link(int x, int y, int v) {
    e[++num] = {y, h[x], v}, h[x] = num;
    e[++num] = {x, h[y], v}, h[y] = num;
  }
  int L[N], R[N];
  struct qy {
    int u, v, l, r, id;
  };
  int size[N], vis[N];
  ;
  inline void dfs0(int x, int fa = 0) {
    size[x] = 1;
    for (int i = h[x]; i; i = e[i].nxt)
      if (!vis[e[i].to] && e[i].to != fa) {
        dfs0(e[i].to, x);
        size[x] += size[e[i].to];
      }
  }
  int min, root;
  inline void dfs1(int x, int s, int fa = 0) {
    int max = s - size[x];
    for (int i = h[x]; i; i = e[i].nxt)
      if (!vis[e[i].to] && e[i].to != fa) {
        dfs1(e[i].to, s, x);
        max = std::max(max, size[e[i].to]);
      }
    if (max < min) min = max, root = x;
  }
  inline int getroot(int x) {
    dfs0(x), min = 1e9, dfs1(x, size[x]);
    return root;
  }
  int sa[N], sb[N];
  int lab[N], dep[N];
  std::vector<qy> p[N];
  inline void dfs2(int x, int sa, int sb, int fa = 0) {
    ::sa[x] = sa;
    ::sb[x] = sb;
    for (int i = h[x]; i; i = e[i].nxt)
      if (!vis[e[i].to] && e[i].to != fa) {
        dfs2(e[i].to, sam.c[sa][e[i].v], rev.c[sb][e[i].v], x);
      }
  }
  inline void dfs3(int x, int lab, int fa = 0) {
    ::lab[x] = lab, dep[x] = dep[fa] + 1;
    for (int i = h[x]; i; i = e[i].nxt)
      if (!vis[e[i].to] && e[i].to != fa) {
        dfs3(e[i].to, lab, x);
      }
  }
  int ans[N];
  inline int count(const BS& x, int l, int r) {
    if (l > r) return 0;
    using unsigned long long = unsigned long long;
    int ans = 0;
    for (; l <= r && l % 64 != 0; ++l) ans += x.test(l);
    for (; l <= r && r % 64 != 63; --r) ans += x.test(r);
    if (l > r) return ans;
    const int L = l / 64, R = r / 64;
    unsigned long long* ARR = (unsigned long long*)&x;
    for (int i = L; i <= R; ++i) ans += __builtin_popcountll(ARR[i]);
    return ans;
  }
  inline void solve(int x, std::vector<qy> o) {
    if (o.empty()) return;
    x = getroot(x);
    dfs2(x, 1, 1);
    vis[x] = 1, dep[x] = 0, lab[x] = 0;
    for (int i = h[x]; i; i = e[i].nxt)
      if (!vis[e[i].to]) {
        dfs3(e[i].to, e[i].to, x);
        p[e[i].to].clear();
      }
    for (const qy& x : o) {
      if (lab[x.u] && lab[x.v] && lab[x.u] == lab[x.v]) {
        p[lab[x.u]].push_back(x);
      } else {
        const BS& a = rev.get(sb[x.u]);
        const BS& b = sam.get(sa[x.v]);
        static BS Z;
        const int len = dep[x.u] + dep[x.v];
        Z.shift(a, len - 1, b);
        ans[x.id] = count(Z, x.l + len - 1, x.r);
      }
    }
    for (int i = h[x]; i; i = e[i].nxt)
      if (!vis[e[i].to]) {
        solve(e[i].to, p[e[i].to]);
        std::vector<qy>().swap(p[e[i].to]);
      }
  }
  int main() {
    std::ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1, u, v; i < n; ++i) {
      char c;
      cin >> u >> v >> c;
      link(u, v, c - 'a');
    }
    std::string T;
    for (int i = 1, o = 0; i <= m; ++i) {
      std::string s;
      cin >> s;
      if (i != m) s += char('a' + 26);
      T += s;
      L[i] = o + 1;
      R[i] = o += s.size();
    }
    for (int i = 1; i <= R[m]; ++i) {
      sam.T[i] = T[i - 1];
      rev.T[i] = T[T.size() - i];
    }
    sam.n = rev.n = R[m];
    sam.init();
    rev.init();
    rev.rev();
    std::vector<qy> o(q);
    for (int i = 0; i < q; ++i) {
      cin >> o[i].u >> o[i].v >> o[i].l >> o[i].r;
      o[i].id = i;
      o[i].l = L[o[i].l];
      o[i].r = R[o[i].r];
    }
    solve(1, o);
    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
  }
  