#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 6e5 + 10;
int n, m, q, k, head[N], tot, st[M], ed[M], ans[N];
char s[M];
struct node {
  int to, nxt;
  char c;
} e[N << 1];
void add(int x, int y, char c) {
  e[++k].to = y;
  e[k].nxt = head[x];
  head[x] = k;
  e[k].c = c;
}
int sz[N], son[N], fa[N], dep[N];
char val[N];
void dfs1(int u, int lst, char c) {
  sz[u] = 1;
  dep[u] = dep[lst] + 1;
  fa[u] = lst;
  val[u] = c;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == lst) continue;
    dfs1(v, u, e[i].c);
    sz[u] += sz[v];
    if (sz[son[u]] < sz[v]) son[u] = v;
  }
}
int top[N], dfn[N], ord[N], cnt, pnt1[N], pnt2[N];
void dfs2(int u, int lst, int tp) {
  dfn[u] = ++cnt;
  ord[cnt] = u;
  top[u] = tp;
  if (son[u]) dfs2(son[u], u, tp);
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == lst || v == son[u]) continue;
    dfs2(v, u, v);
  }
}
int lca(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    x = fa[top[x]];
  }
  if (dep[x] < dep[y]) swap(x, y);
  return y;
}
namespace SA {
int sa[M], rnk[M], x[M], y[M], height[M], c[M], minn[M][20], getlog[M];
void work() {
  int m = 255;
  for (int i = 1; i <= tot; i++) c[x[i] = s[i]]++;
  for (int i = 1; i <= m; i++) c[i] += c[i - 1];
  for (int i = tot; i; i--) sa[c[x[i]]--] = i;
  for (int k = 1; k <= tot; k <<= 1) {
    int now = 0;
    for (int i = tot - k + 1; i <= tot; i++) y[++now] = i;
    for (int i = 1; i <= tot; i++)
      if (sa[i] > k) y[++now] = sa[i] - k;
    for (int i = 1; i <= m; i++) c[i] = 0;
    for (int i = 1; i <= tot; i++) c[x[y[i]]]++;
    for (int i = 1; i <= m; i++) c[i] += c[i - 1];
    for (int i = tot; i; i--) sa[c[x[y[i]]]--] = y[i];
    swap(x, y);
    now = 1;
    x[sa[1]] = 1;
    for (int i = 2; i <= tot; i++)
      x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])
                     ? now
                     : ++now;
    if (now == tot) break;
    m = now;
  }
  for (int i = 1; i <= tot; i++) rnk[sa[i]] = i;
  int k = 0;
  for (int i = 1; i <= tot; i++) {
    if (rnk[i] == 1) continue;
    int j = sa[rnk[i] - 1];
    if (k) k--;
    while (i + k <= tot && j + k <= tot && s[i + k] == s[j + k]) k++;
    height[rnk[i]] = k;
  }
  for (int i = 2; i <= tot; i++) minn[i][0] = height[i];
  for (int j = 1; j <= 19; j++)
    for (int i = 2; i + (1 << j) - 1 <= tot; i++)
      minn[i][j] = min(minn[i][j - 1], minn[i + (1 << j - 1)][j - 1]);
  for (int i = 2; i <= tot; i++) getlog[i] = getlog[i >> 1] + 1;
}
int query(int x, int y) {
  if (x == y) return tot - x + 1;
  x = rnk[x];
  y = rnk[y];
  if (x > y) swap(x, y);
  x++;
  int k = getlog[y - x + 1];
  return min(minn[x][k], minn[y - (1 << k) + 1][k]);
}
}  // namespace SA
vector<pair<int, int> > vec1, vec2, vec;
int comp(int mid) {
  int pos = SA::sa[mid];
  for (auto it : vec) {
    int lcp = SA::query(it.first, pos), len = it.second - it.first + 1;
    if (lcp >= len)
      pos += len;
    else {
      if (s[pos + lcp] < s[it.first + lcp]) return 0;
      return 1;
    }
  }
  return 2;
}
pair<int, int> work(int x, int y) {
  int z = lca(x, y);
  vec1.clear();
  vec2.clear();
  vec.clear();
  while (top[x] != top[z]) {
    vec1.push_back(make_pair(pnt2[x], pnt2[top[x]]));
    x = fa[top[x]];
  }
  if (x != z) vec1.push_back(make_pair(pnt2[x], pnt2[son[z]]));
  while (top[y] != top[z]) {
    vec2.push_back(make_pair(pnt1[top[y]], pnt1[y]));
    y = fa[top[y]];
  }
  if (y != z) vec2.push_back(make_pair(pnt1[son[z]], pnt1[y]));
  reverse(vec2.begin(), vec2.end());
  for (auto it : vec1) vec.push_back(it);
  for (auto it : vec2) vec.push_back(it);
  int l = 1, r = tot, mid, resl = tot + 1;
  while (l <= r) {
    mid = l + r >> 1;
    int tmp = comp(mid);
    if (tmp == 2)
      resl = min(resl, mid), r = mid - 1;
    else if (tmp == 1)
      r = mid - 1;
    else
      l = mid + 1;
  }
  l = 1;
  r = tot;
  int resr = 0;
  while (l <= r) {
    mid = l + r >> 1;
    int tmp = comp(mid);
    if (tmp == 2)
      resr = max(resr, mid), l = mid + 1;
    else if (tmp == 1)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return make_pair(resl, resr);
}
struct data {
  int ql, qr, ord, opt;
  data(int ql = 0, int qr = 0, int ord = 0, int opt = 0)
      : ql(ql), qr(qr), ord(ord), opt(opt) {}
};
vector<data> qry[M];
namespace BIT {
int tr[M];
void update(int x) {
  for (; x <= tot; x += x & (-x)) tr[x]++;
}
int query(int x) {
  int res = 0;
  for (; x; x -= x & (-x)) res += tr[x];
  return res;
}
void work() {
  for (int i = 1; i <= tot; i++) {
    update(SA::sa[i]);
    for (auto it : qry[i])
      ans[it.ord] += it.opt * (query(it.qr) - query(it.ql - 1));
  }
}
}  // namespace BIT
int main() {
  scanf("%d%d%d", &n, &m, &q);
  char tmp[M];
  for (int i = 1, x, y; i < n; i++)
    scanf("%d%d%s", &x, &y, tmp + 1), add(x, y, tmp[1]), add(y, x, tmp[1]);
  for (int i = 1; i <= m; i++) {
    scanf("%s", tmp + 1);
    int len = strlen(tmp + 1);
    st[i] = tot + 1;
    for (int j = 1; j <= len; j++) s[++tot] = tmp[j];
    ed[i] = tot;
    s[++tot] = '#';
  }
  dfs1(1, 1, '$');
  dfs2(1, 1, 1);
  for (int i = 1; i <= n; i++) s[++tot] = val[ord[i]], pnt1[ord[i]] = tot;
  s[++tot] = '#';
  for (int i = n; i; i--) s[++tot] = val[ord[i]], pnt2[ord[i]] = tot;
  SA::work();
  for (int i = 1; i <= q; i++) {
    int u, v, l, r;
    scanf("%d%d%d%d", &u, &v, &l, &r);
    pair<int, int> rge = work(u, v);
    if (rge.first > rge.second)
      ans[i] = 0;
    else {
      qry[rge.first - 1].push_back(data(st[l], ed[r], i, -1));
      qry[rge.second].push_back(data(st[l], ed[r], i, 1));
    }
  }
  BIT::work();
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}

### Prompt

Please create a solution in Cpp 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;
const int N = 1e5 + 10, M = 6e5 + 10;
int n, m, q, k, head[N], tot, st[M], ed[M], ans[N];
char s[M];
struct node {
  int to, nxt;
  char c;
} e[N << 1];
void add(int x, int y, char c) {
  e[++k].to = y;
  e[k].nxt = head[x];
  head[x] = k;
  e[k].c = c;
}
int sz[N], son[N], fa[N], dep[N];
char val[N];
void dfs1(int u, int lst, char c) {
  sz[u] = 1;
  dep[u] = dep[lst] + 1;
  fa[u] = lst;
  val[u] = c;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == lst) continue;
    dfs1(v, u, e[i].c);
    sz[u] += sz[v];
    if (sz[son[u]] < sz[v]) son[u] = v;
  }
}
int top[N], dfn[N], ord[N], cnt, pnt1[N], pnt2[N];
void dfs2(int u, int lst, int tp) {
  dfn[u] = ++cnt;
  ord[cnt] = u;
  top[u] = tp;
  if (son[u]) dfs2(son[u], u, tp);
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == lst || v == son[u]) continue;
    dfs2(v, u, v);
  }
}
int lca(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]]) swap(x, y);
    x = fa[top[x]];
  }
  if (dep[x] < dep[y]) swap(x, y);
  return y;
}
namespace SA {
int sa[M], rnk[M], x[M], y[M], height[M], c[M], minn[M][20], getlog[M];
void work() {
  int m = 255;
  for (int i = 1; i <= tot; i++) c[x[i] = s[i]]++;
  for (int i = 1; i <= m; i++) c[i] += c[i - 1];
  for (int i = tot; i; i--) sa[c[x[i]]--] = i;
  for (int k = 1; k <= tot; k <<= 1) {
    int now = 0;
    for (int i = tot - k + 1; i <= tot; i++) y[++now] = i;
    for (int i = 1; i <= tot; i++)
      if (sa[i] > k) y[++now] = sa[i] - k;
    for (int i = 1; i <= m; i++) c[i] = 0;
    for (int i = 1; i <= tot; i++) c[x[y[i]]]++;
    for (int i = 1; i <= m; i++) c[i] += c[i - 1];
    for (int i = tot; i; i--) sa[c[x[y[i]]]--] = y[i];
    swap(x, y);
    now = 1;
    x[sa[1]] = 1;
    for (int i = 2; i <= tot; i++)
      x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])
                     ? now
                     : ++now;
    if (now == tot) break;
    m = now;
  }
  for (int i = 1; i <= tot; i++) rnk[sa[i]] = i;
  int k = 0;
  for (int i = 1; i <= tot; i++) {
    if (rnk[i] == 1) continue;
    int j = sa[rnk[i] - 1];
    if (k) k--;
    while (i + k <= tot && j + k <= tot && s[i + k] == s[j + k]) k++;
    height[rnk[i]] = k;
  }
  for (int i = 2; i <= tot; i++) minn[i][0] = height[i];
  for (int j = 1; j <= 19; j++)
    for (int i = 2; i + (1 << j) - 1 <= tot; i++)
      minn[i][j] = min(minn[i][j - 1], minn[i + (1 << j - 1)][j - 1]);
  for (int i = 2; i <= tot; i++) getlog[i] = getlog[i >> 1] + 1;
}
int query(int x, int y) {
  if (x == y) return tot - x + 1;
  x = rnk[x];
  y = rnk[y];
  if (x > y) swap(x, y);
  x++;
  int k = getlog[y - x + 1];
  return min(minn[x][k], minn[y - (1 << k) + 1][k]);
}
}  // namespace SA
vector<pair<int, int> > vec1, vec2, vec;
int comp(int mid) {
  int pos = SA::sa[mid];
  for (auto it : vec) {
    int lcp = SA::query(it.first, pos), len = it.second - it.first + 1;
    if (lcp >= len)
      pos += len;
    else {
      if (s[pos + lcp] < s[it.first + lcp]) return 0;
      return 1;
    }
  }
  return 2;
}
pair<int, int> work(int x, int y) {
  int z = lca(x, y);
  vec1.clear();
  vec2.clear();
  vec.clear();
  while (top[x] != top[z]) {
    vec1.push_back(make_pair(pnt2[x], pnt2[top[x]]));
    x = fa[top[x]];
  }
  if (x != z) vec1.push_back(make_pair(pnt2[x], pnt2[son[z]]));
  while (top[y] != top[z]) {
    vec2.push_back(make_pair(pnt1[top[y]], pnt1[y]));
    y = fa[top[y]];
  }
  if (y != z) vec2.push_back(make_pair(pnt1[son[z]], pnt1[y]));
  reverse(vec2.begin(), vec2.end());
  for (auto it : vec1) vec.push_back(it);
  for (auto it : vec2) vec.push_back(it);
  int l = 1, r = tot, mid, resl = tot + 1;
  while (l <= r) {
    mid = l + r >> 1;
    int tmp = comp(mid);
    if (tmp == 2)
      resl = min(resl, mid), r = mid - 1;
    else if (tmp == 1)
      r = mid - 1;
    else
      l = mid + 1;
  }
  l = 1;
  r = tot;
  int resr = 0;
  while (l <= r) {
    mid = l + r >> 1;
    int tmp = comp(mid);
    if (tmp == 2)
      resr = max(resr, mid), l = mid + 1;
    else if (tmp == 1)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return make_pair(resl, resr);
}
struct data {
  int ql, qr, ord, opt;
  data(int ql = 0, int qr = 0, int ord = 0, int opt = 0)
      : ql(ql), qr(qr), ord(ord), opt(opt) {}
};
vector<data> qry[M];
namespace BIT {
int tr[M];
void update(int x) {
  for (; x <= tot; x += x & (-x)) tr[x]++;
}
int query(int x) {
  int res = 0;
  for (; x; x -= x & (-x)) res += tr[x];
  return res;
}
void work() {
  for (int i = 1; i <= tot; i++) {
    update(SA::sa[i]);
    for (auto it : qry[i])
      ans[it.ord] += it.opt * (query(it.qr) - query(it.ql - 1));
  }
}
}  // namespace BIT
int main() {
  scanf("%d%d%d", &n, &m, &q);
  char tmp[M];
  for (int i = 1, x, y; i < n; i++)
    scanf("%d%d%s", &x, &y, tmp + 1), add(x, y, tmp[1]), add(y, x, tmp[1]);
  for (int i = 1; i <= m; i++) {
    scanf("%s", tmp + 1);
    int len = strlen(tmp + 1);
    st[i] = tot + 1;
    for (int j = 1; j <= len; j++) s[++tot] = tmp[j];
    ed[i] = tot;
    s[++tot] = '#';
  }
  dfs1(1, 1, '$');
  dfs2(1, 1, 1);
  for (int i = 1; i <= n; i++) s[++tot] = val[ord[i]], pnt1[ord[i]] = tot;
  s[++tot] = '#';
  for (int i = n; i; i--) s[++tot] = val[ord[i]], pnt2[ord[i]] = tot;
  SA::work();
  for (int i = 1; i <= q; i++) {
    int u, v, l, r;
    scanf("%d%d%d%d", &u, &v, &l, &r);
    pair<int, int> rge = work(u, v);
    if (rge.first > rge.second)
      ans[i] = 0;
    else {
      qry[rge.first - 1].push_back(data(st[l], ed[r], i, -1));
      qry[rge.second].push_back(data(st[l], ed[r], i, 1));
    }
  }
  BIT::work();
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}

```