#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 3) + (x << 1) + (c ^ 48);
    c = getchar();
  }
  return f == -1 ? ~x + 1 : x;
}
int n, m, q;
int tot;
char str[100010], s[400010];
vector<pair<int, int> > vec[100010];
int pw[100010];
const int d = 31, mod = 998244353;
int v1[800010], v2[800010];
int sa[400010], rk[400010], height[400010];
int f[400010][19];
int c[400010];
int logt[400010];
int hsh[400010];
void SA() {
  for (int i = 1; i <= tot; ++i) v1[i] = s[i] - 'a' + 1, ++c[v1[i]];
  for (int i = 2; i <= 27; ++i) c[i] += c[i - 1];
  for (int i = 1; i <= tot; ++i) sa[c[v1[i]]--] = i;
  for (int k = 1; k < tot; k <<= 1) {
    int cnt = 0;
    memset(c, 0, sizeof(c));
    for (int i = tot - k + 1; i <= tot; ++i) v2[++cnt] = i;
    for (int i = 1; i <= tot; ++i)
      if (sa[i] > k) v2[++cnt] = sa[i] - k;
    for (int i = 1; i <= tot; ++i) c[v1[i]]++;
    for (int i = 1; i <= tot; ++i) c[i] += c[i - 1];
    for (int i = tot; i >= 1; --i) {
      sa[c[v1[v2[i]]]--] = v2[i];
      v2[i] = 0;
    }
    swap(v1, v2);
    cnt = 1;
    v1[sa[1]] = 1;
    for (int i = 2; i <= tot; ++i) {
      if (v2[sa[i]] == v2[sa[i - 1]] && v2[sa[i] + k] == v2[sa[i - 1] + k])
        v1[sa[i]] = cnt;
      else
        v1[sa[i]] = ++cnt;
    }
  }
  for (int i = 1; i <= tot; ++i) rk[sa[i]] = i;
  for (int i = 1, j = 0; i <= tot; ++i) {
    if (j) --j;
    while (s[i + j] == s[sa[rk[i] - 1] + j]) ++j;
    height[rk[i]] = j;
  }
  for (int i = 1; i <= tot; ++i) {
    f[i][0] = height[i];
  }
  for (int j = 1; j <= 18; ++j) {
    for (int i = 1; i + (1 << j) - 1 <= tot; ++i) {
      f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
    }
  }
  for (int i = 2; i <= tot; ++i) logt[i] = logt[i >> 1] + 1;
}
int lcp(int x, int y) {
  int l = rk[x], r = rk[y];
  if (l == r) return tot - x + 1;
  if (l > r) swap(l, r);
  ++l;
  int k = logt[r - l + 1];
  return min(f[l][k], f[r - (1 << k) + 1][k]);
}
struct query {
  int l, r, id;
};
vector<query> qr[400010];
int fa[100010], son[100010], dfn[100010], top[100010], idx, rdfn[100010];
int siz[100010], dep[100010];
char vl[100010];
void dfs1(int x, int f) {
  siz[x] = 1;
  dep[x] = dep[f] + 1;
  fa[x] = f;
  for (pair<int, int> i : vec[x]) {
    if (i.first == f) continue;
    vl[i.first] = i.second;
    dfs1(i.first, x);
    siz[x] += siz[i.first];
    if (siz[i.first] > siz[son[x]]) son[x] = i.first;
  }
}
int seq[100010];
void dfs2(int x, int tf) {
  dfn[x] = ++idx;
  s[++tot] = vl[x];
  seq[idx] = x;
  top[x] = tf;
  if (son[x]) {
    dfs2(son[x], tf);
  } else
    return;
  for (pair<int, int> i : vec[x]) {
    if (i.first == fa[x] || i.first == son[x]) continue;
    dfs2(i.first, i.first);
  }
}
struct e {
  int l, r, len;
} up[310], dw[310];
int cu, cd;
int id[400010];
int finds() {
  int l = 1, r = tot, res = 0;
  auto check = [&](int x) {
    int sum = 0;
    for (int i = 1; i <= cu; ++i) {
      int l = lcp(x, up[i].l);
      if (l < up[i].len) {
        return s[x + l] < s[up[i].l + l];
      } else
        x += up[i].len;
    }
    return false;
  };
  while (l <= r) {
    int mid = l + r >> 1;
    if (check(sa[mid]))
      res = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return res;
}
int findb() {
  int l = 1, r = tot, res = tot + 1;
  auto check = [&](int x) {
    for (int i = 1; i <= cu; ++i) {
      int l = lcp(x, up[i].l);
      if (l < up[i].len)
        return s[x + l] > s[up[i].l + l];
      else
        x += up[i].len;
    }
    return false;
  };
  while (l <= r) {
    int mid = l + r >> 1;
    if (check(sa[mid]))
      res = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  return res;
}
int tre[400010];
void upd(int x, int k) {
  while (x <= m) {
    tre[x] += k;
    x += x & -x;
  }
}
int qry(int x) {
  int res = 0;
  while (x) {
    res += tre[x];
    x -= x & -x;
  }
  return res;
}
int ans[100010];
int main() {
  n = read(), m = read(), q = read();
  pw[0] = 1;
  for (int i = 1; i <= n; ++i) pw[i] = 1ll * pw[i - 1] * d % mod;
  for (int i = 1; i < n; ++i) {
    int u = read(), v = read();
    char c = getchar();
    while (c < 'a' || c > 'z') c = getchar();
    vec[u].emplace_back(v, c);
    vec[v].emplace_back(u, c);
  }
  vl[1] = 'a';
  dfs1(1, 0);
  dfs2(1, 0);
  for (int i = n; i >= 1; --i) {
    rdfn[seq[i]] = ++tot;
    s[tot] = vl[seq[i]];
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%s", str + 1);
    s[++tot] = 'z' + 1;
    int l = strlen(str + 1);
    for (int j = 1; j <= l; ++j) s[++tot] = str[j], id[tot] = i;
  }
  SA();
  for (int i = 1; i <= q; ++i) {
    cu = cd = 0;
    int u = read(), v = read(), l = read(), r = read();
    while (top[u] != top[v]) {
      if (dep[top[u]] < dep[top[v]]) {
        dw[++cd] = e{dfn[top[v]], dfn[v]};
        v = fa[top[v]];
      } else {
        up[++cu] = e{rdfn[u], rdfn[top[u]]};
        u = fa[top[u]];
      }
    }
    if (dep[u] > dep[v])
      up[++cu] = e{rdfn[u], rdfn[v] - 1};
    else if (dep[u] < dep[v])
      dw[++cd] = e{dfn[u] + 1, dfn[v]};
    for (int i = cd; i >= 1; --i) up[++cu] = dw[i];
    for (int i = 1; i <= cu; ++i) up[i].len = up[i].r - up[i].l + 1;
    int L = finds() + 1, R = findb() - 1;
    if (L <= R) {
      qr[L - 1].push_back(query{l, r, -i});
      qr[R].push_back(query{l, r, i});
    }
  }
  for (int i = 1; i <= tot; ++i) {
    if (id[sa[i]]) upd(id[sa[i]], 1);
    for (query j : qr[i]) {
      int res = qry(j.r) - qry(j.l - 1);
      if (j.id < 0)
        ans[-j.id] -= res;
      else
        ans[j.id] += res;
    }
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
}

### Prompt

Develop a solution in CPP 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;
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 3) + (x << 1) + (c ^ 48);
    c = getchar();
  }
  return f == -1 ? ~x + 1 : x;
}
int n, m, q;
int tot;
char str[100010], s[400010];
vector<pair<int, int> > vec[100010];
int pw[100010];
const int d = 31, mod = 998244353;
int v1[800010], v2[800010];
int sa[400010], rk[400010], height[400010];
int f[400010][19];
int c[400010];
int logt[400010];
int hsh[400010];
void SA() {
  for (int i = 1; i <= tot; ++i) v1[i] = s[i] - 'a' + 1, ++c[v1[i]];
  for (int i = 2; i <= 27; ++i) c[i] += c[i - 1];
  for (int i = 1; i <= tot; ++i) sa[c[v1[i]]--] = i;
  for (int k = 1; k < tot; k <<= 1) {
    int cnt = 0;
    memset(c, 0, sizeof(c));
    for (int i = tot - k + 1; i <= tot; ++i) v2[++cnt] = i;
    for (int i = 1; i <= tot; ++i)
      if (sa[i] > k) v2[++cnt] = sa[i] - k;
    for (int i = 1; i <= tot; ++i) c[v1[i]]++;
    for (int i = 1; i <= tot; ++i) c[i] += c[i - 1];
    for (int i = tot; i >= 1; --i) {
      sa[c[v1[v2[i]]]--] = v2[i];
      v2[i] = 0;
    }
    swap(v1, v2);
    cnt = 1;
    v1[sa[1]] = 1;
    for (int i = 2; i <= tot; ++i) {
      if (v2[sa[i]] == v2[sa[i - 1]] && v2[sa[i] + k] == v2[sa[i - 1] + k])
        v1[sa[i]] = cnt;
      else
        v1[sa[i]] = ++cnt;
    }
  }
  for (int i = 1; i <= tot; ++i) rk[sa[i]] = i;
  for (int i = 1, j = 0; i <= tot; ++i) {
    if (j) --j;
    while (s[i + j] == s[sa[rk[i] - 1] + j]) ++j;
    height[rk[i]] = j;
  }
  for (int i = 1; i <= tot; ++i) {
    f[i][0] = height[i];
  }
  for (int j = 1; j <= 18; ++j) {
    for (int i = 1; i + (1 << j) - 1 <= tot; ++i) {
      f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
    }
  }
  for (int i = 2; i <= tot; ++i) logt[i] = logt[i >> 1] + 1;
}
int lcp(int x, int y) {
  int l = rk[x], r = rk[y];
  if (l == r) return tot - x + 1;
  if (l > r) swap(l, r);
  ++l;
  int k = logt[r - l + 1];
  return min(f[l][k], f[r - (1 << k) + 1][k]);
}
struct query {
  int l, r, id;
};
vector<query> qr[400010];
int fa[100010], son[100010], dfn[100010], top[100010], idx, rdfn[100010];
int siz[100010], dep[100010];
char vl[100010];
void dfs1(int x, int f) {
  siz[x] = 1;
  dep[x] = dep[f] + 1;
  fa[x] = f;
  for (pair<int, int> i : vec[x]) {
    if (i.first == f) continue;
    vl[i.first] = i.second;
    dfs1(i.first, x);
    siz[x] += siz[i.first];
    if (siz[i.first] > siz[son[x]]) son[x] = i.first;
  }
}
int seq[100010];
void dfs2(int x, int tf) {
  dfn[x] = ++idx;
  s[++tot] = vl[x];
  seq[idx] = x;
  top[x] = tf;
  if (son[x]) {
    dfs2(son[x], tf);
  } else
    return;
  for (pair<int, int> i : vec[x]) {
    if (i.first == fa[x] || i.first == son[x]) continue;
    dfs2(i.first, i.first);
  }
}
struct e {
  int l, r, len;
} up[310], dw[310];
int cu, cd;
int id[400010];
int finds() {
  int l = 1, r = tot, res = 0;
  auto check = [&](int x) {
    int sum = 0;
    for (int i = 1; i <= cu; ++i) {
      int l = lcp(x, up[i].l);
      if (l < up[i].len) {
        return s[x + l] < s[up[i].l + l];
      } else
        x += up[i].len;
    }
    return false;
  };
  while (l <= r) {
    int mid = l + r >> 1;
    if (check(sa[mid]))
      res = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return res;
}
int findb() {
  int l = 1, r = tot, res = tot + 1;
  auto check = [&](int x) {
    for (int i = 1; i <= cu; ++i) {
      int l = lcp(x, up[i].l);
      if (l < up[i].len)
        return s[x + l] > s[up[i].l + l];
      else
        x += up[i].len;
    }
    return false;
  };
  while (l <= r) {
    int mid = l + r >> 1;
    if (check(sa[mid]))
      res = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  return res;
}
int tre[400010];
void upd(int x, int k) {
  while (x <= m) {
    tre[x] += k;
    x += x & -x;
  }
}
int qry(int x) {
  int res = 0;
  while (x) {
    res += tre[x];
    x -= x & -x;
  }
  return res;
}
int ans[100010];
int main() {
  n = read(), m = read(), q = read();
  pw[0] = 1;
  for (int i = 1; i <= n; ++i) pw[i] = 1ll * pw[i - 1] * d % mod;
  for (int i = 1; i < n; ++i) {
    int u = read(), v = read();
    char c = getchar();
    while (c < 'a' || c > 'z') c = getchar();
    vec[u].emplace_back(v, c);
    vec[v].emplace_back(u, c);
  }
  vl[1] = 'a';
  dfs1(1, 0);
  dfs2(1, 0);
  for (int i = n; i >= 1; --i) {
    rdfn[seq[i]] = ++tot;
    s[tot] = vl[seq[i]];
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%s", str + 1);
    s[++tot] = 'z' + 1;
    int l = strlen(str + 1);
    for (int j = 1; j <= l; ++j) s[++tot] = str[j], id[tot] = i;
  }
  SA();
  for (int i = 1; i <= q; ++i) {
    cu = cd = 0;
    int u = read(), v = read(), l = read(), r = read();
    while (top[u] != top[v]) {
      if (dep[top[u]] < dep[top[v]]) {
        dw[++cd] = e{dfn[top[v]], dfn[v]};
        v = fa[top[v]];
      } else {
        up[++cu] = e{rdfn[u], rdfn[top[u]]};
        u = fa[top[u]];
      }
    }
    if (dep[u] > dep[v])
      up[++cu] = e{rdfn[u], rdfn[v] - 1};
    else if (dep[u] < dep[v])
      dw[++cd] = e{dfn[u] + 1, dfn[v]};
    for (int i = cd; i >= 1; --i) up[++cu] = dw[i];
    for (int i = 1; i <= cu; ++i) up[i].len = up[i].r - up[i].l + 1;
    int L = finds() + 1, R = findb() - 1;
    if (L <= R) {
      qr[L - 1].push_back(query{l, r, -i});
      qr[R].push_back(query{l, r, i});
    }
  }
  for (int i = 1; i <= tot; ++i) {
    if (id[sa[i]]) upd(id[sa[i]], 1);
    for (query j : qr[i]) {
      int res = qry(j.r) - qry(j.l - 1);
      if (j.id < 0)
        ans[-j.id] -= res;
      else
        ans[j.id] += res;
    }
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
}

```