#include <bits/stdc++.h>
using namespace std;
int n, m, q;
int A[400005], N, Aid[400005], pos1[100005], pos2[100005];
vector<pair<int, int> > tr[600005];
char c[100005];
int sa[400005], rk[400005], lcp[400005];
int st[20][400005], lg[400005];
int hson[100005], dfn[100005], nxt[100005];
int fa[100005], sz[100005], tot;
int ans[100005], L[100005], R[100005];
vector<pair<int, int> > qry[400005];
vector<pair<int, int> > v1, v2;
int bit[100005];
struct SuffixArray {
  int m, num[400005], nsa[400005];
  int get(int p, int x) { return p + x > N ? 0 : rk[p + x]; }
  void qsort(int x, int *a, int *b, int m) {
    memset(num, 0, (m + 2) << 2);
    for (int i = 1; i <= N; i++) num[get(i, x)]++;
    for (int i = 1; i <= m; i++) num[i] += num[i - 1];
    for (int i = N; i; i--) b[num[get(a[i], x)]--] = a[i];
  }
  bool cmp(int a, int b, int x) {
    if (rk[a] != rk[b]) return rk[a] < rk[b];
    return get(a, x) < get(b, x);
  }
  void solve() {
    int m = 27;
    for (int i = 1; i <= N; i++) rk[i] = A[i], nsa[i] = i;
    qsort(0, nsa, sa, m);
    num[sa[1]] = m = 1;
    for (int i = 2; i <= N; i++) m += cmp(sa[i - 1], sa[i], 0), num[sa[i]] = m;
    for (int i = 1; i <= N; i++) rk[i] = num[i];
    for (int k = 1; m < N; k <<= 1) {
      qsort(k, sa, nsa, m), qsort(0, nsa, sa, m);
      num[sa[1]] = m = 1;
      for (int i = 2; i <= N; i++)
        m += cmp(sa[i - 1], sa[i], k), num[sa[i]] = m;
      memcpy(rk + 1, num + 1, (N + 2) << 2);
    }
    for (int i = 1; i <= N; i++) {
      if (i > 1) lg[i] = lg[i >> 1] + 1;
      if (rk[i] > 1) {
        lcp[rk[i]] = max(lcp[rk[i - 1]], 1);
        while (max(i, sa[rk[i] - 1]) + lcp[rk[i]] - 1 <= N &&
               A[i + lcp[rk[i]] - 1] == A[sa[rk[i] - 1] + lcp[rk[i]] - 1])
          lcp[rk[i]]++;
        lcp[rk[i]]--;
      }
    }
    for (int i = 1; i <= N; i++) st[0][i] = lcp[i];
    for (int i = 1; i <= lg[N]; i++)
      for (int j = 1; j + (1 << i) - 1 <= N; j++)
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
  }
  int qry(int l, int r) {
    if (l == r) return N - sa[l] + 1;
    if (r < l) swap(l, r);
    int Lg = lg[r - l];
    return min(st[Lg][l + 1], st[Lg][r - (1 << Lg) + 1]);
  }
} saSolver;
struct Hld {
  void dfs1(int u) {
    sz[u] = 1;
    for (auto [v, w] : tr[u])
      if (v != fa[u]) {
        fa[v] = u, dfs1(v);
        sz[u] += sz[v];
        if (sz[v] > sz[hson[u]]) hson[u] = v;
      }
  }
  void dfs2(int u) {
    dfn[u] = ++tot;
    if (hson[u]) nxt[hson[u]] = nxt[u], dfs2(hson[u]);
    for (auto [v, w] : tr[u])
      if (v != fa[u] && v != hson[u]) nxt[v] = v, dfs2(v);
  }
  void DFS1(int u) {
    int W;
    for (auto [v, w] : tr[u]) {
      if (v != fa[u] && v != hson[u]) {
        DFS1(v);
        A[++N] = w, pos1[dfn[v]] = N;
      }
      if (v == hson[u]) W = w;
    }
    if (hson[u]) {
      DFS1(hson[u]);
      A[++N] = W, pos1[dfn[hson[u]]] = N;
    }
  }
  void DFS2(int u) {
    int W;
    for (auto [v, w] : tr[u])
      if (v == hson[u]) W = w;
    if (hson[u]) {
      A[++N] = W, pos2[dfn[hson[u]]] = N;
      DFS2(hson[u]);
    }
    for (auto [v, w] : tr[u])
      if (v != fa[u] && v != hson[u]) {
        A[++N] = w, pos2[dfn[v]] = N;
        DFS2(v);
      }
  }
  void solve() {
    dfs1(1);
    dfs2(1);
    DFS1(1);
    DFS2(1);
  }
  bool cmp(int l, int r, int a) { return dfn[l] <= dfn[a] && dfn[a] <= dfn[r]; }
  int qry(int u, int v) {
    for (;;) {
      if (dfn[u] > dfn[v]) swap(u, v);
      if (cmp(nxt[v], v, u)) return u;
      v = fa[nxt[v]];
    }
  }
  void calc(int u, int t, vector<pair<int, int> > &v) {
    for (;;) {
      if (u == t) return;
      if (cmp(nxt[u], u, t)) {
        v.push_back({dfn[t] + 1, dfn[u]});
        return;
      }
      v.push_back({dfn[nxt[u]], dfn[u]}), u = fa[nxt[u]];
      ;
    }
  }
} hldSolver;
struct BIT {
  void upd(int i) {
    for (; i <= m; i += i & -i) bit[i]++;
  }
  int ask(int i) {
    int res = 0;
    for (; i; i -= i & -i) res += bit[i];
    return res;
  }
  int qry(int l, int r) { return ask(r) - ask(l - 1); }
} bitSolver;
bool check1(int p, int L, int l, int r, int ld, int rd) {
  if (p > rd) return 1;
  if (sa[p] + L > N) return 0;
  p = sa[p] + L;
  int tmp = saSolver.qry(rk[p], rk[l]);
  if (tmp >= r - l + 1) return 1;
  return A[p + tmp] > A[l + tmp];
}
bool check2(int p, int L, int l, int r, int ld, int rd) {
  if (sa[p] + L > N || p < ld) return 1;
  p = sa[p] + L;
  int tmp = saSolver.qry(rk[p], rk[l]);
  if (tmp >= r - l + 1) return 1;
  return A[p + tmp] < A[l + tmp];
}
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i < n; i++) {
    int u, v;
    char buf[3];
    scanf("%d%d%s", &u, &v, buf);
    buf[0] = buf[0] - 'a' + 1;
    tr[u].push_back({v, *buf});
    tr[v].push_back({u, *buf});
  }
  for (int i = 1; i <= m; i++) {
    scanf("%s", c + 1);
    int len = strlen(c + 1);
    for (int j = 1; j <= len; j++) A[++N] = c[j] - 'a' + 1, Aid[N] = i;
    A[++N] = 27;
  }
  hldSolver.solve();
  saSolver.solve();
  for (int i = 1; i <= q; i++) {
    int u, v;
    scanf("%d%d%d%d", &u, &v, &L[i], &R[i]);
    int Lca = hldSolver.qry(u, v);
    v1.clear(), v2.clear();
    hldSolver.calc(u, Lca, v1);
    hldSolver.calc(v, Lca, v2), reverse(v2.begin(), v2.end());
    int L = 1, R = N, Len = 0, ld, rd;
    for (auto [x, y] : v1) {
      int l = pos1[y], r = pos1[y] + (y - x);
      ld = L - 1, rd = N + 1;
      while (rd > ld + 1) {
        int md = (ld + rd) >> 1;
        if (check1(md, Len, l, r, L, R))
          rd = md;
        else
          ld = md;
      }
      int LL = rd;
      ld = 0, rd = R + 1;
      while (rd > ld + 1) {
        int md = (ld + rd) >> 1;
        if (check2(md, Len, l, r, L, R))
          ld = md;
        else
          rd = md;
      }
      int RR = ld;
      L = LL, R = RR;
      if (L > R) break;
      Len += r - l + 1;
    }
    for (auto [x, y] : v2) {
      int l = pos2[x], r = pos2[x] + (y - x);
      ld = L - 1, rd = N + 1;
      while (rd > ld + 1) {
        int md = (ld + rd) >> 1;
        if (check1(md, Len, l, r, L, R))
          rd = md;
        else
          ld = md;
      }
      int LL = rd;
      ld = 0, rd = R + 1;
      while (rd > ld + 1) {
        int md = (ld + rd) >> 1;
        if (check2(md, Len, l, r, L, R))
          ld = md;
        else
          rd = md;
      }
      int RR = ld;
      L = LL, R = RR;
      if (L > R) break;
      Len += r - l + 1;
    }
    if (L <= R) {
      qry[L - 1].push_back({i, -1});
      qry[R].push_back({i, 1});
    }
  }
  for (int i = 1; i <= N; i++) {
    if (Aid[sa[i]]) bitSolver.upd(Aid[sa[i]]);
    for (auto [x, c] : qry[i]) ans[x] += c * bitSolver.qry(L[x], R[x]);
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}

### Prompt

In CPP, your task is to solve the following problem:

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;
int n, m, q;
int A[400005], N, Aid[400005], pos1[100005], pos2[100005];
vector<pair<int, int> > tr[600005];
char c[100005];
int sa[400005], rk[400005], lcp[400005];
int st[20][400005], lg[400005];
int hson[100005], dfn[100005], nxt[100005];
int fa[100005], sz[100005], tot;
int ans[100005], L[100005], R[100005];
vector<pair<int, int> > qry[400005];
vector<pair<int, int> > v1, v2;
int bit[100005];
struct SuffixArray {
  int m, num[400005], nsa[400005];
  int get(int p, int x) { return p + x > N ? 0 : rk[p + x]; }
  void qsort(int x, int *a, int *b, int m) {
    memset(num, 0, (m + 2) << 2);
    for (int i = 1; i <= N; i++) num[get(i, x)]++;
    for (int i = 1; i <= m; i++) num[i] += num[i - 1];
    for (int i = N; i; i--) b[num[get(a[i], x)]--] = a[i];
  }
  bool cmp(int a, int b, int x) {
    if (rk[a] != rk[b]) return rk[a] < rk[b];
    return get(a, x) < get(b, x);
  }
  void solve() {
    int m = 27;
    for (int i = 1; i <= N; i++) rk[i] = A[i], nsa[i] = i;
    qsort(0, nsa, sa, m);
    num[sa[1]] = m = 1;
    for (int i = 2; i <= N; i++) m += cmp(sa[i - 1], sa[i], 0), num[sa[i]] = m;
    for (int i = 1; i <= N; i++) rk[i] = num[i];
    for (int k = 1; m < N; k <<= 1) {
      qsort(k, sa, nsa, m), qsort(0, nsa, sa, m);
      num[sa[1]] = m = 1;
      for (int i = 2; i <= N; i++)
        m += cmp(sa[i - 1], sa[i], k), num[sa[i]] = m;
      memcpy(rk + 1, num + 1, (N + 2) << 2);
    }
    for (int i = 1; i <= N; i++) {
      if (i > 1) lg[i] = lg[i >> 1] + 1;
      if (rk[i] > 1) {
        lcp[rk[i]] = max(lcp[rk[i - 1]], 1);
        while (max(i, sa[rk[i] - 1]) + lcp[rk[i]] - 1 <= N &&
               A[i + lcp[rk[i]] - 1] == A[sa[rk[i] - 1] + lcp[rk[i]] - 1])
          lcp[rk[i]]++;
        lcp[rk[i]]--;
      }
    }
    for (int i = 1; i <= N; i++) st[0][i] = lcp[i];
    for (int i = 1; i <= lg[N]; i++)
      for (int j = 1; j + (1 << i) - 1 <= N; j++)
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
  }
  int qry(int l, int r) {
    if (l == r) return N - sa[l] + 1;
    if (r < l) swap(l, r);
    int Lg = lg[r - l];
    return min(st[Lg][l + 1], st[Lg][r - (1 << Lg) + 1]);
  }
} saSolver;
struct Hld {
  void dfs1(int u) {
    sz[u] = 1;
    for (auto [v, w] : tr[u])
      if (v != fa[u]) {
        fa[v] = u, dfs1(v);
        sz[u] += sz[v];
        if (sz[v] > sz[hson[u]]) hson[u] = v;
      }
  }
  void dfs2(int u) {
    dfn[u] = ++tot;
    if (hson[u]) nxt[hson[u]] = nxt[u], dfs2(hson[u]);
    for (auto [v, w] : tr[u])
      if (v != fa[u] && v != hson[u]) nxt[v] = v, dfs2(v);
  }
  void DFS1(int u) {
    int W;
    for (auto [v, w] : tr[u]) {
      if (v != fa[u] && v != hson[u]) {
        DFS1(v);
        A[++N] = w, pos1[dfn[v]] = N;
      }
      if (v == hson[u]) W = w;
    }
    if (hson[u]) {
      DFS1(hson[u]);
      A[++N] = W, pos1[dfn[hson[u]]] = N;
    }
  }
  void DFS2(int u) {
    int W;
    for (auto [v, w] : tr[u])
      if (v == hson[u]) W = w;
    if (hson[u]) {
      A[++N] = W, pos2[dfn[hson[u]]] = N;
      DFS2(hson[u]);
    }
    for (auto [v, w] : tr[u])
      if (v != fa[u] && v != hson[u]) {
        A[++N] = w, pos2[dfn[v]] = N;
        DFS2(v);
      }
  }
  void solve() {
    dfs1(1);
    dfs2(1);
    DFS1(1);
    DFS2(1);
  }
  bool cmp(int l, int r, int a) { return dfn[l] <= dfn[a] && dfn[a] <= dfn[r]; }
  int qry(int u, int v) {
    for (;;) {
      if (dfn[u] > dfn[v]) swap(u, v);
      if (cmp(nxt[v], v, u)) return u;
      v = fa[nxt[v]];
    }
  }
  void calc(int u, int t, vector<pair<int, int> > &v) {
    for (;;) {
      if (u == t) return;
      if (cmp(nxt[u], u, t)) {
        v.push_back({dfn[t] + 1, dfn[u]});
        return;
      }
      v.push_back({dfn[nxt[u]], dfn[u]}), u = fa[nxt[u]];
      ;
    }
  }
} hldSolver;
struct BIT {
  void upd(int i) {
    for (; i <= m; i += i & -i) bit[i]++;
  }
  int ask(int i) {
    int res = 0;
    for (; i; i -= i & -i) res += bit[i];
    return res;
  }
  int qry(int l, int r) { return ask(r) - ask(l - 1); }
} bitSolver;
bool check1(int p, int L, int l, int r, int ld, int rd) {
  if (p > rd) return 1;
  if (sa[p] + L > N) return 0;
  p = sa[p] + L;
  int tmp = saSolver.qry(rk[p], rk[l]);
  if (tmp >= r - l + 1) return 1;
  return A[p + tmp] > A[l + tmp];
}
bool check2(int p, int L, int l, int r, int ld, int rd) {
  if (sa[p] + L > N || p < ld) return 1;
  p = sa[p] + L;
  int tmp = saSolver.qry(rk[p], rk[l]);
  if (tmp >= r - l + 1) return 1;
  return A[p + tmp] < A[l + tmp];
}
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i < n; i++) {
    int u, v;
    char buf[3];
    scanf("%d%d%s", &u, &v, buf);
    buf[0] = buf[0] - 'a' + 1;
    tr[u].push_back({v, *buf});
    tr[v].push_back({u, *buf});
  }
  for (int i = 1; i <= m; i++) {
    scanf("%s", c + 1);
    int len = strlen(c + 1);
    for (int j = 1; j <= len; j++) A[++N] = c[j] - 'a' + 1, Aid[N] = i;
    A[++N] = 27;
  }
  hldSolver.solve();
  saSolver.solve();
  for (int i = 1; i <= q; i++) {
    int u, v;
    scanf("%d%d%d%d", &u, &v, &L[i], &R[i]);
    int Lca = hldSolver.qry(u, v);
    v1.clear(), v2.clear();
    hldSolver.calc(u, Lca, v1);
    hldSolver.calc(v, Lca, v2), reverse(v2.begin(), v2.end());
    int L = 1, R = N, Len = 0, ld, rd;
    for (auto [x, y] : v1) {
      int l = pos1[y], r = pos1[y] + (y - x);
      ld = L - 1, rd = N + 1;
      while (rd > ld + 1) {
        int md = (ld + rd) >> 1;
        if (check1(md, Len, l, r, L, R))
          rd = md;
        else
          ld = md;
      }
      int LL = rd;
      ld = 0, rd = R + 1;
      while (rd > ld + 1) {
        int md = (ld + rd) >> 1;
        if (check2(md, Len, l, r, L, R))
          ld = md;
        else
          rd = md;
      }
      int RR = ld;
      L = LL, R = RR;
      if (L > R) break;
      Len += r - l + 1;
    }
    for (auto [x, y] : v2) {
      int l = pos2[x], r = pos2[x] + (y - x);
      ld = L - 1, rd = N + 1;
      while (rd > ld + 1) {
        int md = (ld + rd) >> 1;
        if (check1(md, Len, l, r, L, R))
          rd = md;
        else
          ld = md;
      }
      int LL = rd;
      ld = 0, rd = R + 1;
      while (rd > ld + 1) {
        int md = (ld + rd) >> 1;
        if (check2(md, Len, l, r, L, R))
          ld = md;
        else
          rd = md;
      }
      int RR = ld;
      L = LL, R = RR;
      if (L > R) break;
      Len += r - l + 1;
    }
    if (L <= R) {
      qry[L - 1].push_back({i, -1});
      qry[R].push_back({i, 1});
    }
  }
  for (int i = 1; i <= N; i++) {
    if (Aid[sa[i]]) bitSolver.upd(Aid[sa[i]]);
    for (auto [x, c] : qry[i]) ans[x] += c * bitSolver.qry(L[x], R[x]);
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}

```