#include <bits/stdc++.h>
using namespace std;
const int P = 998244853;
int ad(int k1, int k2) { return k1 += k2 - P, k1 += k1 >> 31 & P; }
int su(int k1, int k2) { return k1 -= k2, k1 += k1 >> 31 & P; }
int mu(int k1, int k2) { return 1LL * k1 * k2 % P; }
void uad(int& k1, int k2) { k1 += k2 - P, k1 += k1 >> 31 & P; }
void usu(int& k1, int k2) { k1 -= k2, k1 += k1 >> 31 & P; }
template <class... T>
int ad(int k1, T... k2) {
  return ad(k1, ad(k2...));
}
template <class... T>
int su(int k1, T... k2) {
  return su(k1, ad(k2...));
}
template <class... T>
int mu(int k1, T... k2) {
  return mu(k1, mu(k2...));
}
template <class... T>
void uad(int& k1, T... k2) {
  return uad(k1, ad(k2...));
}
template <class... T>
void usu(int& k1, T... k2) {
  return usu(k1, ad(k2...));
}
int po(int k1, int k2) {
  int k3 = 1;
  for (; k2; k2 >>= 1, k1 = mu(k1, k1))
    if (k2 & 1) k3 = mu(k3, k1);
  return k3;
}
const int N = 200005, B = 31, K = 18, INF = 0X3F3F3F3F;
int n, m, Q, in[N], out[N], pw[N * 2], ans[N];
char ss[N];
vector<pair<int, char> > e[N];
int up[N / 2][K], dep[N];
struct hash_t {
  int v, len;
  bool operator==(const hash_t& k) const { return len == k.len && v == k.v; }
  hash_t operator+(const hash_t& k) const {
    return (hash_t){ad(mu(v, pw[k.len]), k.v), len + k.len};
  }
} f[N / 2][K], g[N / 2][K], hss[N];
hash_t ghs(int l, int r) {
  if (l == 0) return hss[r];
  return (hash_t){su(hss[r].v, mu(hss[l - 1].v, pw[r - l + 1])), r - l + 1};
}
int LCA(int u, int v) {
  if (dep[u] < dep[v]) {
    swap(u, v);
  }
  int dt = dep[u] - dep[v];
  for (int i = (K - 1); i >= (0); --i)
    if (dt >> i & 1) u = up[u][i];
  if (u == v) return u;
  for (int i = (K - 1); i >= (0); --i)
    if (up[u][i] != up[v][i]) {
      u = up[u][i];
      v = up[v][i];
    }
  return up[u][0];
}
int kth_fa(int u, int k) {
  for (int i = (K - 1); i >= (0); --i)
    if (k >> i & 1) u = up[u][i];
  return u;
}
hash_t get_hash(int u, int v) {
  hash_t a = (hash_t){0, 0}, b = (hash_t){0, 0};
  if (dep[u] > dep[v]) {
    int dt = dep[u] - dep[v];
    for (int i = (K - 1); i >= (0); --i)
      if (dt >> i & 1) {
        a = a + f[u][i];
        u = up[u][i];
      }
  }
  if (dep[v] > dep[u]) {
    int dt = dep[v] - dep[u];
    for (int i = (K - 1); i >= (0); --i)
      if (dt >> i & 1) {
        b = g[v][i] + b;
        v = up[v][i];
      }
  }
  if (u == v) return a + b;
  for (int i = (K - 1); i >= (0); --i)
    if (up[u][i] != up[v][i]) {
      a = a + f[u][i];
      b = g[v][i] + b;
      u = up[u][i];
      v = up[v][i];
    }
  return a + f[u][0] + f[v][0] + b;
}
hash_t asks(int u, int v, int lca, int lim) {
  if (dep[v] - dep[lca] >= lim) {
    return get_hash(kth_fa(v, lim), v);
  } else {
    lim -= dep[v] - dep[lca];
    if (lim >= 0 && lim <= dep[u] - dep[lca]) {
      return get_hash(kth_fa(u, dep[u] - dep[lca] - lim), lca) +
             get_hash(lca, v);
    } else {
      return (hash_t){-1, -1};
    }
  }
}
char fa_ch[N];
int find_ch(int u, int v, int lca, int lim) {
  if (dep[v] - dep[lca] >= lim) {
    return fa_ch[kth_fa(v, lim - 1)];
  } else {
    lim -= dep[v] - dep[lca];
    return fa_ch[kth_fa(u, dep[u] - dep[lca] - lim)];
  }
}
void dfs1(int u, int father, char father_c) {
  up[u][0] = father, dep[u] = dep[father] + 1, fa_ch[u] = father_c;
  if (father) {
    f[u][0] = g[u][0] = (hash_t){father_c - 'a' + 1, 1};
  }
  for (int i = (1); i <= (K - 1); ++i) {
    up[u][i] = up[up[u][i - 1]][i - 1];
    if (up[u][i]) {
      f[u][i] = f[u][i - 1] + f[up[u][i - 1]][i - 1];
      g[u][i] = g[up[u][i - 1]][i - 1] + g[u][i - 1];
    }
  }
  for (auto& _ : e[u]) {
    int v;
    char c;
    tie(v, c) = _;
    if (v != father) {
      dfs1(v, u, c);
    }
  }
}
struct SAM {
  int cnt, lst, fa[N * 2], ch[N * 2][27], len[N * 2], pos[N * 2], right[N * 2],
      fuck_sz[N * 2], fuck_son[N * 2];
  vector<tuple<int, char> > e[N * 2];
  SAM() { cnt = lst = 1; }
  void ps(int c, int pos0) {
    int p = lst, np = lst = ++cnt;
    len[np] = len[p] + 1, pos[np] = pos0;
    for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
    if (!p) {
      fa[np] = 1;
      return;
    }
    int q = ch[p][c];
    if (len[p] + 1 == len[q]) {
      fa[np] = q;
      return;
    }
    int nq = ++cnt;
    len[nq] = len[p] + 1;
    memcpy(ch[nq], ch[q], sizeof(ch[nq]));
    fa[nq] = fa[q], fa[q] = fa[np] = nq;
    for (; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
  }
  vector<tuple<int, int, int> > fucks[N * 2];
  void dfs(int k1) {
    fuck_sz[k1] = 1, right[k1] = pos[k1];
    for (auto& _ : e[k1]) {
      int x;
      tie(x, ignore) = _;
      dfs(x);
      fuck_sz[k1] += fuck_sz[x];
      if (fuck_sz[x] > fuck_sz[fuck_son[k1]]) {
        fuck_son[k1] = x;
      }
      if (!right[k1]) {
        right[k1] = right[x];
      }
      get<1>(_) = ss[right[x] - len[k1]];
    }
  }
  void bud() {
    for (int i = (2); i <= (cnt); ++i) e[fa[i]].emplace_back(i, 0);
    dfs(1);
  }
  int sz[N * 2], f[N * 2], full, root;
  bool ban[N * 2];
  void get_root(int u, int father) {
    sz[u] = 1, f[u] = 0;
    for (auto& _ : e[u]) {
      int v;
      tie(v, ignore) = _;
      if (!ban[v] && v != father) {
        get_root(v, u);
        sz[u] += sz[v];
        if (f[u] < sz[v]) f[u] = sz[v];
      }
    }
    if (f[u] < full - f[u]) f[u] = full - f[u];
    if (f[u] < f[root]) root = u;
  }
  void get_ans(int L, int R, int u, int id) {
    L = in[L], R = out[R];
    fucks[u].emplace_back(L, R, id);
  }
  void sol(int u, const vector<tuple<int, int, int, int, int, int> >& qs) {
    ban[u] = 1;
    int old = full;
    vector<vector<tuple<int, int, int, int, int, int> > > vec(
        ((int)(e[u]).size()) + 1);
    for (auto& x : qs) {
      int dis = dep[get<0>(x)] + dep[get<1>(x)] - dep[get<2>(x)] * 2;
      if (u == 1 || (len[fa[u]] + 1 <= dis &&
                     asks(get<0>(x), get<1>(x), get<2>(x), len[fa[u]] + 1) ==
                         ghs(right[u] - len[fa[u]], right[u]))) {
        if (len[fa[u]] + 1 <= dis && dis <= len[u]) {
          if (get_hash(get<0>(x), get<1>(x)) ==
              ghs(right[u] - dis + 1, right[u])) {
            get_ans(get<3>(x), get<4>(x), u, get<5>(x));
          }
        } else if (asks(get<0>(x), get<1>(x), get<2>(x), len[u]) ==
                   ghs(right[u] - len[u] + 1, right[u])) {
          int ch = find_ch(get<0>(x), get<1>(x), get<2>(x), len[u] + 1);
          for (int i = (0); i <= (((int)(e[u]).size()) - 1); ++i)
            if (get<1>(e[u][i]) == ch) {
              vec[i].push_back(x);
              break;
            }
        }
      } else {
        vec[((int)(e[u]).size())].push_back(x);
      }
    }
    for (int i = (0); i <= (((int)(e[u]).size())); ++i) {
      int v = i == ((int)(e[u]).size()) ? fa[u] : get<0>(e[u][i]);
      if (v && !ban[v]) {
        full = sz[v] < sz[u] ? sz[v] : old - sz[u];
        root = 0;
        int vv = v;
        while (vv != 1 && !ban[fa[vv]]) vv = fa[vv];
        get_root(vv, 0);
        sol(root, vec[i]);
      }
    }
  }
  struct fuck_tree {
    int t[N * 2];
    void upd(int fuck, int x) {
      for (int i = fuck; i < N * 2; i += i & -i) {
        t[i] += x;
      }
    }
    int qry(int fuck) {
      int fucks = 0;
      for (int i = fuck; i; i &= i - 1) {
        fucks += t[i];
      }
      return fucks;
    }
    int qry(int fuck_l, int fuck_r) { return qry(fuck_r) - qry(fuck_l - 1); }
  } t;
  void fuck_up(int u, int x) {
    if (pos[u]) t.upd(pos[u], x);
    for (auto& _ : e[u]) {
      int v;
      tie(v, ignore) = _;
      fuck_up(v, x);
    }
  }
  void fuck(int u) {
    for (auto& _ : e[u]) {
      int v;
      tie(v, ignore) = _;
      if (v != fuck_son[u]) {
        fuck(v);
        fuck_up(v, -1);
      }
    }
    if (fuck_son[u]) {
      fuck(fuck_son[u]);
    }
    for (auto& _ : e[u]) {
      int v;
      tie(v, ignore) = _;
      if (v != fuck_son[u]) {
        fuck_up(v, 1);
      }
    }
    if (pos[u]) t.upd(pos[u], 1);
    for (auto& x : fucks[u]) {
      ans[get<2>(x)] += t.qry(get<0>(x), get<1>(x));
    }
  }
  void main(const vector<tuple<int, int, int, int, int, int> >& qs) {
    f[0] = INF;
    root = 0;
    full = cnt;
    get_root(1, 0);
    ((void)0);
    sol(root, qs);
    ((void)0);
    fuck(1);
  }
} A;
int main() {
  pw[0] = 1;
  for (int i = (1); i <= (N * 2 - 1); ++i) pw[i] = mu(pw[i - 1], B);
  scanf("%d%d%d", &n, &m, &Q);
  for (int i = (2); i <= (n); ++i) {
    int u, v, c;
    scanf("%d%d", &u, &v);
    while (!islower(c = getchar()))
      ;
    e[u].emplace_back(v, c);
    e[v].emplace_back(u, c);
  }
  dfs1(1, 0, 0);
  int len = 0;
  static char s[N];
  for (int i = (1); i <= (m); ++i) {
    scanf("%s", s);
    int ll = strlen(s);
    in[i] = len + 1;
    for (int j = 0; j < ll; ++j) {
      A.ps(s[j] - 'a', ++len);
      ss[len] = s[j];
    }
    A.ps('z' - 'a' + 1, ++len);
    ss[len] = 'z' + 1;
    out[i] = len;
  }
  for (int i = (1); i <= (len); ++i) {
    hss[i] = hss[i - 1] + (hash_t){ss[i] - 'a' + 1, 1};
  }
  A.bud();
  vector<tuple<int, int, int, int, int, int> > qs;
  for (int _ = (1); _ <= (Q); ++_) {
    int u, v, l, r;
    scanf("%d%d%d%d", &u, &v, &l, &r);
    qs.emplace_back(u, v, LCA(u, v), l, r, _);
  }
  A.main(qs);
  for (int i = (1); i <= (Q); ++i) printf("%d\n", ans[i]);
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int P = 998244853;
int ad(int k1, int k2) { return k1 += k2 - P, k1 += k1 >> 31 & P; }
int su(int k1, int k2) { return k1 -= k2, k1 += k1 >> 31 & P; }
int mu(int k1, int k2) { return 1LL * k1 * k2 % P; }
void uad(int& k1, int k2) { k1 += k2 - P, k1 += k1 >> 31 & P; }
void usu(int& k1, int k2) { k1 -= k2, k1 += k1 >> 31 & P; }
template <class... T>
int ad(int k1, T... k2) {
  return ad(k1, ad(k2...));
}
template <class... T>
int su(int k1, T... k2) {
  return su(k1, ad(k2...));
}
template <class... T>
int mu(int k1, T... k2) {
  return mu(k1, mu(k2...));
}
template <class... T>
void uad(int& k1, T... k2) {
  return uad(k1, ad(k2...));
}
template <class... T>
void usu(int& k1, T... k2) {
  return usu(k1, ad(k2...));
}
int po(int k1, int k2) {
  int k3 = 1;
  for (; k2; k2 >>= 1, k1 = mu(k1, k1))
    if (k2 & 1) k3 = mu(k3, k1);
  return k3;
}
const int N = 200005, B = 31, K = 18, INF = 0X3F3F3F3F;
int n, m, Q, in[N], out[N], pw[N * 2], ans[N];
char ss[N];
vector<pair<int, char> > e[N];
int up[N / 2][K], dep[N];
struct hash_t {
  int v, len;
  bool operator==(const hash_t& k) const { return len == k.len && v == k.v; }
  hash_t operator+(const hash_t& k) const {
    return (hash_t){ad(mu(v, pw[k.len]), k.v), len + k.len};
  }
} f[N / 2][K], g[N / 2][K], hss[N];
hash_t ghs(int l, int r) {
  if (l == 0) return hss[r];
  return (hash_t){su(hss[r].v, mu(hss[l - 1].v, pw[r - l + 1])), r - l + 1};
}
int LCA(int u, int v) {
  if (dep[u] < dep[v]) {
    swap(u, v);
  }
  int dt = dep[u] - dep[v];
  for (int i = (K - 1); i >= (0); --i)
    if (dt >> i & 1) u = up[u][i];
  if (u == v) return u;
  for (int i = (K - 1); i >= (0); --i)
    if (up[u][i] != up[v][i]) {
      u = up[u][i];
      v = up[v][i];
    }
  return up[u][0];
}
int kth_fa(int u, int k) {
  for (int i = (K - 1); i >= (0); --i)
    if (k >> i & 1) u = up[u][i];
  return u;
}
hash_t get_hash(int u, int v) {
  hash_t a = (hash_t){0, 0}, b = (hash_t){0, 0};
  if (dep[u] > dep[v]) {
    int dt = dep[u] - dep[v];
    for (int i = (K - 1); i >= (0); --i)
      if (dt >> i & 1) {
        a = a + f[u][i];
        u = up[u][i];
      }
  }
  if (dep[v] > dep[u]) {
    int dt = dep[v] - dep[u];
    for (int i = (K - 1); i >= (0); --i)
      if (dt >> i & 1) {
        b = g[v][i] + b;
        v = up[v][i];
      }
  }
  if (u == v) return a + b;
  for (int i = (K - 1); i >= (0); --i)
    if (up[u][i] != up[v][i]) {
      a = a + f[u][i];
      b = g[v][i] + b;
      u = up[u][i];
      v = up[v][i];
    }
  return a + f[u][0] + f[v][0] + b;
}
hash_t asks(int u, int v, int lca, int lim) {
  if (dep[v] - dep[lca] >= lim) {
    return get_hash(kth_fa(v, lim), v);
  } else {
    lim -= dep[v] - dep[lca];
    if (lim >= 0 && lim <= dep[u] - dep[lca]) {
      return get_hash(kth_fa(u, dep[u] - dep[lca] - lim), lca) +
             get_hash(lca, v);
    } else {
      return (hash_t){-1, -1};
    }
  }
}
char fa_ch[N];
int find_ch(int u, int v, int lca, int lim) {
  if (dep[v] - dep[lca] >= lim) {
    return fa_ch[kth_fa(v, lim - 1)];
  } else {
    lim -= dep[v] - dep[lca];
    return fa_ch[kth_fa(u, dep[u] - dep[lca] - lim)];
  }
}
void dfs1(int u, int father, char father_c) {
  up[u][0] = father, dep[u] = dep[father] + 1, fa_ch[u] = father_c;
  if (father) {
    f[u][0] = g[u][0] = (hash_t){father_c - 'a' + 1, 1};
  }
  for (int i = (1); i <= (K - 1); ++i) {
    up[u][i] = up[up[u][i - 1]][i - 1];
    if (up[u][i]) {
      f[u][i] = f[u][i - 1] + f[up[u][i - 1]][i - 1];
      g[u][i] = g[up[u][i - 1]][i - 1] + g[u][i - 1];
    }
  }
  for (auto& _ : e[u]) {
    int v;
    char c;
    tie(v, c) = _;
    if (v != father) {
      dfs1(v, u, c);
    }
  }
}
struct SAM {
  int cnt, lst, fa[N * 2], ch[N * 2][27], len[N * 2], pos[N * 2], right[N * 2],
      fuck_sz[N * 2], fuck_son[N * 2];
  vector<tuple<int, char> > e[N * 2];
  SAM() { cnt = lst = 1; }
  void ps(int c, int pos0) {
    int p = lst, np = lst = ++cnt;
    len[np] = len[p] + 1, pos[np] = pos0;
    for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
    if (!p) {
      fa[np] = 1;
      return;
    }
    int q = ch[p][c];
    if (len[p] + 1 == len[q]) {
      fa[np] = q;
      return;
    }
    int nq = ++cnt;
    len[nq] = len[p] + 1;
    memcpy(ch[nq], ch[q], sizeof(ch[nq]));
    fa[nq] = fa[q], fa[q] = fa[np] = nq;
    for (; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
  }
  vector<tuple<int, int, int> > fucks[N * 2];
  void dfs(int k1) {
    fuck_sz[k1] = 1, right[k1] = pos[k1];
    for (auto& _ : e[k1]) {
      int x;
      tie(x, ignore) = _;
      dfs(x);
      fuck_sz[k1] += fuck_sz[x];
      if (fuck_sz[x] > fuck_sz[fuck_son[k1]]) {
        fuck_son[k1] = x;
      }
      if (!right[k1]) {
        right[k1] = right[x];
      }
      get<1>(_) = ss[right[x] - len[k1]];
    }
  }
  void bud() {
    for (int i = (2); i <= (cnt); ++i) e[fa[i]].emplace_back(i, 0);
    dfs(1);
  }
  int sz[N * 2], f[N * 2], full, root;
  bool ban[N * 2];
  void get_root(int u, int father) {
    sz[u] = 1, f[u] = 0;
    for (auto& _ : e[u]) {
      int v;
      tie(v, ignore) = _;
      if (!ban[v] && v != father) {
        get_root(v, u);
        sz[u] += sz[v];
        if (f[u] < sz[v]) f[u] = sz[v];
      }
    }
    if (f[u] < full - f[u]) f[u] = full - f[u];
    if (f[u] < f[root]) root = u;
  }
  void get_ans(int L, int R, int u, int id) {
    L = in[L], R = out[R];
    fucks[u].emplace_back(L, R, id);
  }
  void sol(int u, const vector<tuple<int, int, int, int, int, int> >& qs) {
    ban[u] = 1;
    int old = full;
    vector<vector<tuple<int, int, int, int, int, int> > > vec(
        ((int)(e[u]).size()) + 1);
    for (auto& x : qs) {
      int dis = dep[get<0>(x)] + dep[get<1>(x)] - dep[get<2>(x)] * 2;
      if (u == 1 || (len[fa[u]] + 1 <= dis &&
                     asks(get<0>(x), get<1>(x), get<2>(x), len[fa[u]] + 1) ==
                         ghs(right[u] - len[fa[u]], right[u]))) {
        if (len[fa[u]] + 1 <= dis && dis <= len[u]) {
          if (get_hash(get<0>(x), get<1>(x)) ==
              ghs(right[u] - dis + 1, right[u])) {
            get_ans(get<3>(x), get<4>(x), u, get<5>(x));
          }
        } else if (asks(get<0>(x), get<1>(x), get<2>(x), len[u]) ==
                   ghs(right[u] - len[u] + 1, right[u])) {
          int ch = find_ch(get<0>(x), get<1>(x), get<2>(x), len[u] + 1);
          for (int i = (0); i <= (((int)(e[u]).size()) - 1); ++i)
            if (get<1>(e[u][i]) == ch) {
              vec[i].push_back(x);
              break;
            }
        }
      } else {
        vec[((int)(e[u]).size())].push_back(x);
      }
    }
    for (int i = (0); i <= (((int)(e[u]).size())); ++i) {
      int v = i == ((int)(e[u]).size()) ? fa[u] : get<0>(e[u][i]);
      if (v && !ban[v]) {
        full = sz[v] < sz[u] ? sz[v] : old - sz[u];
        root = 0;
        int vv = v;
        while (vv != 1 && !ban[fa[vv]]) vv = fa[vv];
        get_root(vv, 0);
        sol(root, vec[i]);
      }
    }
  }
  struct fuck_tree {
    int t[N * 2];
    void upd(int fuck, int x) {
      for (int i = fuck; i < N * 2; i += i & -i) {
        t[i] += x;
      }
    }
    int qry(int fuck) {
      int fucks = 0;
      for (int i = fuck; i; i &= i - 1) {
        fucks += t[i];
      }
      return fucks;
    }
    int qry(int fuck_l, int fuck_r) { return qry(fuck_r) - qry(fuck_l - 1); }
  } t;
  void fuck_up(int u, int x) {
    if (pos[u]) t.upd(pos[u], x);
    for (auto& _ : e[u]) {
      int v;
      tie(v, ignore) = _;
      fuck_up(v, x);
    }
  }
  void fuck(int u) {
    for (auto& _ : e[u]) {
      int v;
      tie(v, ignore) = _;
      if (v != fuck_son[u]) {
        fuck(v);
        fuck_up(v, -1);
      }
    }
    if (fuck_son[u]) {
      fuck(fuck_son[u]);
    }
    for (auto& _ : e[u]) {
      int v;
      tie(v, ignore) = _;
      if (v != fuck_son[u]) {
        fuck_up(v, 1);
      }
    }
    if (pos[u]) t.upd(pos[u], 1);
    for (auto& x : fucks[u]) {
      ans[get<2>(x)] += t.qry(get<0>(x), get<1>(x));
    }
  }
  void main(const vector<tuple<int, int, int, int, int, int> >& qs) {
    f[0] = INF;
    root = 0;
    full = cnt;
    get_root(1, 0);
    ((void)0);
    sol(root, qs);
    ((void)0);
    fuck(1);
  }
} A;
int main() {
  pw[0] = 1;
  for (int i = (1); i <= (N * 2 - 1); ++i) pw[i] = mu(pw[i - 1], B);
  scanf("%d%d%d", &n, &m, &Q);
  for (int i = (2); i <= (n); ++i) {
    int u, v, c;
    scanf("%d%d", &u, &v);
    while (!islower(c = getchar()))
      ;
    e[u].emplace_back(v, c);
    e[v].emplace_back(u, c);
  }
  dfs1(1, 0, 0);
  int len = 0;
  static char s[N];
  for (int i = (1); i <= (m); ++i) {
    scanf("%s", s);
    int ll = strlen(s);
    in[i] = len + 1;
    for (int j = 0; j < ll; ++j) {
      A.ps(s[j] - 'a', ++len);
      ss[len] = s[j];
    }
    A.ps('z' - 'a' + 1, ++len);
    ss[len] = 'z' + 1;
    out[i] = len;
  }
  for (int i = (1); i <= (len); ++i) {
    hss[i] = hss[i - 1] + (hash_t){ss[i] - 'a' + 1, 1};
  }
  A.bud();
  vector<tuple<int, int, int, int, int, int> > qs;
  for (int _ = (1); _ <= (Q); ++_) {
    int u, v, l, r;
    scanf("%d%d%d%d", &u, &v, &l, &r);
    qs.emplace_back(u, v, LCA(u, v), l, r, _);
  }
  A.main(qs);
  for (int i = (1); i <= (Q); ++i) printf("%d\n", ans[i]);
  return 0;
}

```