#include <bits/stdc++.h>
using namespace std;
int sa[200010], x[200010 << 1], y[200010], sl[200010], N;
void getsa(int n, int m, char zf[200010]) {
  N = n;
  for (int i = 0; i < n; i++) sl[x[i] = zf[i]] += 1;
  for (int i = 1; i <= m; i++) sl[i] += sl[i - 1];
  for (int i = n - 1; i >= 0; i--) sa[--sl[x[i]]] = i;
  for (int mi = 1; mi <= n; mi *= 2) {
    int s = 0;
    for (int i = n - mi; i < n; i++) y[s++] = i;
    for (int i = 0; i < n; i++) {
      if (sa[i] >= mi) y[s++] = sa[i] - mi;
    }
    for (int i = 1; i <= m; i++) sl[i] = 0;
    for (int i = 0; i < n; i++) sl[x[i]] += 1;
    for (int i = 1; i <= m; i++) sl[i] += sl[i - 1];
    for (int i = n - 1; i >= 0; i--) sa[--sl[x[y[i]]]] = y[i];
    m = 1;
    for (int i = 0; i < n; i++) {
      if (i != 0 &&
          (x[sa[i]] != x[sa[i - 1]] || x[sa[i] + mi] != x[sa[i - 1] + mi]))
        m += 1;
      y[sa[i]] = m;
    }
    if (m == n) break;
    for (int i = 0; i < n; i++) x[i] = y[i];
  }
}
unsigned long long ha[200010], mi[200010], hz[200010], H[100010];
char S[200010], ch[100010], fb[100010];
int st[100010], wz[100010], sd[100010], cd[100010];
unsigned long long getha1(int l, int r) {
  if (l == 0) return ha[r];
  return ha[r] - ha[l - 1] * mi[r - l + 1];
}
unsigned long long getha2(int l, int r) {
  return hz[l] - hz[r + 1] * mi[r - l + 1];
}
unsigned long long getha3(int a, int b) {
  return H[a] - H[b] * mi[sd[a] - sd[b]];
}
int lg[100010], bz[17][100010], le[100010], top[100010], son[100010],
    fa[100010];
vector<int> li[100010], up[100010], ve[100010];
vector<char> vw[100010];
void addb(int a, int b, char c) {
  ve[a].push_back(b);
  vw[a].push_back(c);
}
int dfs(int u, int f) {
  sd[u] = sd[f] + 1;
  fa[u] = f;
  int mx = 0;
  son[u] = -1;
  for (int i = 0; i < ve[u].size(); i++) {
    int t = ve[u][i];
    if (t == f) continue;
    H[t] = H[u] * 20060915 + vw[u][i];
    fb[t] = vw[u][i];
    int rt = dfs(t, u);
    if (rt > mx) mx = rt, son[u] = t;
  }
  return le[u] = mx + 1;
}
void dfs2(int u, int f, int tp) {
  top[u] = tp;
  if (son[u] == -1) return;
  dfs2(son[u], u, tp);
  for (int i : ve[u]) {
    if (i != son[u] && i != f) dfs2(i, u, i);
  }
}
void yucl(int n) {
  dfs(1, 0);
  dfs2(1, 0, 1);
  for (int i = 1; i <= n; i++) {
    int x = 0;
    while ((2 << x) <= i) x += 1;
    lg[i] = x;
    bz[0][i] = fa[i];
  }
  for (int i = 1; i <= 16; i++) {
    for (int j = 1; j <= n; j++) bz[i][j] = bz[i - 1][bz[i - 1][j]];
  }
  for (int i = 1; i <= n; i++) {
    if (i == son[fa[i]]) continue;
    for (int s = 0, u = i; s < le[i]; s++, u = son[u]) li[i].push_back(u);
    for (int s = 0, u = i; s < le[i]; s++, u = fa[u]) up[i].push_back(u);
  }
}
int getkth(int x, int k) {
  if (k == 0) return x;
  int g = lg[k];
  x = bz[g][x];
  k ^= (1 << g);
  int s = sd[x] - k - sd[top[x]];
  if (s >= 0) return li[top[x]][s];
  return up[top[x]][-s];
}
int cmp1(int u, int x) {
  for (int i = 16; i >= 0; i--) {
    if (bz[i][u] == 0 || (x + (1 << i)) > N) continue;
    if (getha3(u, bz[i][u]) == getha2(x, x + (1 << i) - 1))
      u = bz[i][u], x += (1 << i);
  }
  return (int)fb[u] - S[x];
}
int cmp2(int c, int u, int x) {
  if (x + (sd[u] - sd[c]) <= N &&
      getha3(u, c) == getha1(x, x + (sd[u] - sd[c]) - 1))
    return 0;
  for (int i = 16; i >= 0; i--) {
    if ((1 << i) > (sd[u] - sd[c]) || (x + (1 << i)) > N) continue;
    int t = getkth(u, (sd[u] - sd[c]) - (1 << i));
    if (getha3(t, c) == getha1(x, x + (1 << i) - 1)) c = t, x += (1 << i);
  }
  u = getkth(u, sd[u] - sd[c] - 1);
  return (int)fb[u] - S[x];
}
int getlca(int x, int y) {
  if (sd[x] < sd[y]) {
    int t = x;
    x = y;
    y = t;
  }
  for (int i = 16; i >= 0; i--) {
    if (sd[bz[i][x]] >= sd[y]) x = bz[i][x];
  }
  int rt;
  if (x == y) return x;
  for (int i = 16; i >= 0; i--) {
    if (bz[i][x] != bz[i][y])
      x = bz[i][x], y = bz[i][y];
    else
      rt = bz[i][x];
  }
  return rt;
}
int compare(int u, int v, int x) {
  int c = getlca(u, v);
  if (x + (sd[u] - sd[c]) <= N &&
      getha3(u, c) == getha2(x, x + (sd[u] - sd[c]) - 1))
    return cmp2(c, v, x + (sd[u] - sd[c]));
  return cmp1(u, x);
}
int efcz1(int u, int v) {
  int l = 0, r = N;
  while (l < r) {
    int m = (l + r) >> 1;
    if (compare(u, v, sa[m]) <= 0)
      r = m;
    else
      l = m + 1;
  }
  return l;
}
int efcz2(int u, int v) {
  int l = -1, r = N - 1;
  while (l < r) {
    int m = (l + r + 1) >> 1;
    if (compare(u, v, sa[m]) >= 0)
      l = m;
    else
      r = m - 1;
  }
  return l;
}
int cl[10000010], cr[10000010], su[10000010], ss = 0;
int build(int l, int r) {
  int rt = ++ss;
  if (l + 1 == r) return rt;
  int m = (l + r) >> 1;
  cl[rt] = build(l, m);
  cr[rt] = build(m, r);
  return rt;
}
int modify(int i, int l, int r, int j) {
  int rt = ++ss;
  cl[rt] = cl[i];
  cr[rt] = cr[i];
  su[rt] = su[i] + 1;
  if (l + 1 == r) return rt;
  int m = (l + r) >> 1;
  if (j < m)
    cl[rt] = modify(cl[i], l, m, j);
  else
    cr[rt] = modify(cr[i], m, r, j);
  return rt;
}
int sum(int i, int l, int r, int L, int R) {
  if (r <= L || R <= l) return 0;
  if (L <= l && r <= R) return su[i];
  int m = (l + r) >> 1;
  return sum(cl[i], l, m, L, R) + sum(cr[i], m, r, L, R);
}
int ro[200010];
int main() {
  int n, m, q, k = 0;
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    char c[2];
    scanf("%d%d%s", &a, &b, c);
    addb(a, b, c[0]);
    addb(b, a, c[0]);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%s", ch);
    int c = strlen(ch);
    st[i] = k;
    cd[i] = c;
    for (int j = 0; j < c; j++) S[k + j] = ch[j];
    S[k + c] = 1;
    k += c + 1;
  }
  getsa(k, 'z', S);
  mi[0] = 1;
  for (int i = 1; i <= n || i <= k; i++) mi[i] = mi[i - 1] * 20060915;
  for (int i = 0; i < k; i++) {
    if (i > 0) ha[i] = ha[i - 1] * 20060915;
    ha[i] += S[i];
  }
  for (int i = k - 1; i >= 0; i--) hz[i] = hz[i + 1] * 20060915 + S[i];
  yucl(n);
  ro[0] = build(0, k);
  for (int i = 1; i <= k; i++) ro[i] = modify(ro[i - 1], 0, k, sa[i - 1]);
  for (int i = 0; i < q; i++) {
    int u, v, l, r;
    scanf("%d%d%d%d", &u, &v, &l, &r);
    int L = st[l], R = st[r] + cd[r];
    int wl = efcz1(u, v) + 1, wr = efcz2(u, v) + 1;
    int ans = 0;
    if (wl <= wr)
      ans = sum(ro[wr], 0, k, L, R + 1) - sum(ro[wl - 1], 0, k, L, R + 1);
    printf("%d\n", ans);
  }
  return 0;
}

### Prompt

Your task is to create a cpp solution to 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 sa[200010], x[200010 << 1], y[200010], sl[200010], N;
void getsa(int n, int m, char zf[200010]) {
  N = n;
  for (int i = 0; i < n; i++) sl[x[i] = zf[i]] += 1;
  for (int i = 1; i <= m; i++) sl[i] += sl[i - 1];
  for (int i = n - 1; i >= 0; i--) sa[--sl[x[i]]] = i;
  for (int mi = 1; mi <= n; mi *= 2) {
    int s = 0;
    for (int i = n - mi; i < n; i++) y[s++] = i;
    for (int i = 0; i < n; i++) {
      if (sa[i] >= mi) y[s++] = sa[i] - mi;
    }
    for (int i = 1; i <= m; i++) sl[i] = 0;
    for (int i = 0; i < n; i++) sl[x[i]] += 1;
    for (int i = 1; i <= m; i++) sl[i] += sl[i - 1];
    for (int i = n - 1; i >= 0; i--) sa[--sl[x[y[i]]]] = y[i];
    m = 1;
    for (int i = 0; i < n; i++) {
      if (i != 0 &&
          (x[sa[i]] != x[sa[i - 1]] || x[sa[i] + mi] != x[sa[i - 1] + mi]))
        m += 1;
      y[sa[i]] = m;
    }
    if (m == n) break;
    for (int i = 0; i < n; i++) x[i] = y[i];
  }
}
unsigned long long ha[200010], mi[200010], hz[200010], H[100010];
char S[200010], ch[100010], fb[100010];
int st[100010], wz[100010], sd[100010], cd[100010];
unsigned long long getha1(int l, int r) {
  if (l == 0) return ha[r];
  return ha[r] - ha[l - 1] * mi[r - l + 1];
}
unsigned long long getha2(int l, int r) {
  return hz[l] - hz[r + 1] * mi[r - l + 1];
}
unsigned long long getha3(int a, int b) {
  return H[a] - H[b] * mi[sd[a] - sd[b]];
}
int lg[100010], bz[17][100010], le[100010], top[100010], son[100010],
    fa[100010];
vector<int> li[100010], up[100010], ve[100010];
vector<char> vw[100010];
void addb(int a, int b, char c) {
  ve[a].push_back(b);
  vw[a].push_back(c);
}
int dfs(int u, int f) {
  sd[u] = sd[f] + 1;
  fa[u] = f;
  int mx = 0;
  son[u] = -1;
  for (int i = 0; i < ve[u].size(); i++) {
    int t = ve[u][i];
    if (t == f) continue;
    H[t] = H[u] * 20060915 + vw[u][i];
    fb[t] = vw[u][i];
    int rt = dfs(t, u);
    if (rt > mx) mx = rt, son[u] = t;
  }
  return le[u] = mx + 1;
}
void dfs2(int u, int f, int tp) {
  top[u] = tp;
  if (son[u] == -1) return;
  dfs2(son[u], u, tp);
  for (int i : ve[u]) {
    if (i != son[u] && i != f) dfs2(i, u, i);
  }
}
void yucl(int n) {
  dfs(1, 0);
  dfs2(1, 0, 1);
  for (int i = 1; i <= n; i++) {
    int x = 0;
    while ((2 << x) <= i) x += 1;
    lg[i] = x;
    bz[0][i] = fa[i];
  }
  for (int i = 1; i <= 16; i++) {
    for (int j = 1; j <= n; j++) bz[i][j] = bz[i - 1][bz[i - 1][j]];
  }
  for (int i = 1; i <= n; i++) {
    if (i == son[fa[i]]) continue;
    for (int s = 0, u = i; s < le[i]; s++, u = son[u]) li[i].push_back(u);
    for (int s = 0, u = i; s < le[i]; s++, u = fa[u]) up[i].push_back(u);
  }
}
int getkth(int x, int k) {
  if (k == 0) return x;
  int g = lg[k];
  x = bz[g][x];
  k ^= (1 << g);
  int s = sd[x] - k - sd[top[x]];
  if (s >= 0) return li[top[x]][s];
  return up[top[x]][-s];
}
int cmp1(int u, int x) {
  for (int i = 16; i >= 0; i--) {
    if (bz[i][u] == 0 || (x + (1 << i)) > N) continue;
    if (getha3(u, bz[i][u]) == getha2(x, x + (1 << i) - 1))
      u = bz[i][u], x += (1 << i);
  }
  return (int)fb[u] - S[x];
}
int cmp2(int c, int u, int x) {
  if (x + (sd[u] - sd[c]) <= N &&
      getha3(u, c) == getha1(x, x + (sd[u] - sd[c]) - 1))
    return 0;
  for (int i = 16; i >= 0; i--) {
    if ((1 << i) > (sd[u] - sd[c]) || (x + (1 << i)) > N) continue;
    int t = getkth(u, (sd[u] - sd[c]) - (1 << i));
    if (getha3(t, c) == getha1(x, x + (1 << i) - 1)) c = t, x += (1 << i);
  }
  u = getkth(u, sd[u] - sd[c] - 1);
  return (int)fb[u] - S[x];
}
int getlca(int x, int y) {
  if (sd[x] < sd[y]) {
    int t = x;
    x = y;
    y = t;
  }
  for (int i = 16; i >= 0; i--) {
    if (sd[bz[i][x]] >= sd[y]) x = bz[i][x];
  }
  int rt;
  if (x == y) return x;
  for (int i = 16; i >= 0; i--) {
    if (bz[i][x] != bz[i][y])
      x = bz[i][x], y = bz[i][y];
    else
      rt = bz[i][x];
  }
  return rt;
}
int compare(int u, int v, int x) {
  int c = getlca(u, v);
  if (x + (sd[u] - sd[c]) <= N &&
      getha3(u, c) == getha2(x, x + (sd[u] - sd[c]) - 1))
    return cmp2(c, v, x + (sd[u] - sd[c]));
  return cmp1(u, x);
}
int efcz1(int u, int v) {
  int l = 0, r = N;
  while (l < r) {
    int m = (l + r) >> 1;
    if (compare(u, v, sa[m]) <= 0)
      r = m;
    else
      l = m + 1;
  }
  return l;
}
int efcz2(int u, int v) {
  int l = -1, r = N - 1;
  while (l < r) {
    int m = (l + r + 1) >> 1;
    if (compare(u, v, sa[m]) >= 0)
      l = m;
    else
      r = m - 1;
  }
  return l;
}
int cl[10000010], cr[10000010], su[10000010], ss = 0;
int build(int l, int r) {
  int rt = ++ss;
  if (l + 1 == r) return rt;
  int m = (l + r) >> 1;
  cl[rt] = build(l, m);
  cr[rt] = build(m, r);
  return rt;
}
int modify(int i, int l, int r, int j) {
  int rt = ++ss;
  cl[rt] = cl[i];
  cr[rt] = cr[i];
  su[rt] = su[i] + 1;
  if (l + 1 == r) return rt;
  int m = (l + r) >> 1;
  if (j < m)
    cl[rt] = modify(cl[i], l, m, j);
  else
    cr[rt] = modify(cr[i], m, r, j);
  return rt;
}
int sum(int i, int l, int r, int L, int R) {
  if (r <= L || R <= l) return 0;
  if (L <= l && r <= R) return su[i];
  int m = (l + r) >> 1;
  return sum(cl[i], l, m, L, R) + sum(cr[i], m, r, L, R);
}
int ro[200010];
int main() {
  int n, m, q, k = 0;
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    char c[2];
    scanf("%d%d%s", &a, &b, c);
    addb(a, b, c[0]);
    addb(b, a, c[0]);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%s", ch);
    int c = strlen(ch);
    st[i] = k;
    cd[i] = c;
    for (int j = 0; j < c; j++) S[k + j] = ch[j];
    S[k + c] = 1;
    k += c + 1;
  }
  getsa(k, 'z', S);
  mi[0] = 1;
  for (int i = 1; i <= n || i <= k; i++) mi[i] = mi[i - 1] * 20060915;
  for (int i = 0; i < k; i++) {
    if (i > 0) ha[i] = ha[i - 1] * 20060915;
    ha[i] += S[i];
  }
  for (int i = k - 1; i >= 0; i--) hz[i] = hz[i + 1] * 20060915 + S[i];
  yucl(n);
  ro[0] = build(0, k);
  for (int i = 1; i <= k; i++) ro[i] = modify(ro[i - 1], 0, k, sa[i - 1]);
  for (int i = 0; i < q; i++) {
    int u, v, l, r;
    scanf("%d%d%d%d", &u, &v, &l, &r);
    int L = st[l], R = st[r] + cd[r];
    int wl = efcz1(u, v) + 1, wr = efcz2(u, v) + 1;
    int ans = 0;
    if (wl <= wr)
      ans = sum(ro[wr], 0, k, L, R + 1) - sum(ro[wl - 1], 0, k, L, R + 1);
    printf("%d\n", ans);
  }
  return 0;
}

```