#include <bits/stdc++.h>
using namespace std;
void read(int& x) {
  static char c;
  int f = 0;
  while (!isdigit(c = getchar()))
    if (c == '-') f = 1;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
  if (f) x = -x;
}
void chkmax(int& x, int y) {
  if (y > x) x = y;
}
void chkmin(int& x, int y) {
  if (y < x) x = y;
}
void chkmax(long long& x, long long y) {
  if (y > x) x = y;
}
void chkmin(long long& x, long long y) {
  if (y < x) x = y;
}
const int N = 2e5 + 10;
int n, m, q;
vector<pair<int, char> > Edge[N];
int L, bel[N];
char S[N], str[N];
void Insert(int pos, int len) {
  for (int i = 1; i <= len; ++i) S[++L] = str[i], bel[L] = pos;
  S[++L] = 'z' + 1;
}
pair<int, int> charInter[27];
namespace SA {
int sa[N], rk[N], id[N], px[N], oldrk[N * 2], height[N], Buc[N];
bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
void getSA() {
  int m = 300, p = 300;
  for (int i = 1; i <= L; ++i) ++Buc[rk[i] = S[i] - 'a' + 1];
  for (int i = 1; i <= m; ++i) Buc[i] += Buc[i - 1];
  for (int i = 1; i <= 26; ++i)
    charInter[i] = make_pair(Buc[i - 1] + 1, Buc[i]);
  for (int i = L; i; --i) sa[Buc[rk[i]]--] = i;
  for (int w = 1; w < L; w <<= 1) {
    for (int i = 1; i <= m; ++i) Buc[i] = 0;
    m = p, p = 0;
    for (int i = L; i > L - w; --i) id[++p] = i;
    for (int i = 1; i <= L; ++i)
      if (sa[i] > w) id[++p] = sa[i] - w;
    for (int i = 1; i <= L; ++i) ++Buc[px[i] = rk[id[i]]];
    for (int i = 1; i <= m; ++i) Buc[i] += Buc[i - 1];
    for (int i = L; i; --i) sa[Buc[px[i]]--] = id[i];
    memcpy(oldrk, rk, sizeof rk), p = 0;
    for (int i = 1; i <= L; ++i) rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
    if (p == L) {
      for (int i = 1; i <= L; ++i) sa[rk[i]] = i;
      break;
    }
  }
}
bool comp(int pos, int mid, int w) {
  if (sa[mid] + w > L) return false;
  return pos <= rk[sa[mid] + w];
}
pair<int, int> Merge(pair<int, int> L, pair<int, int> R, int w) {
  int _l = L.first, _r = L.second;
  int l, r, mid;
  l = _l, r = _r;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (comp(R.first, mid, w))
      r = mid - 1;
    else
      _l = mid, l = mid + 1;
  }
  if (!comp(R.first, _l, w)) ++_l;
  l = _l, r = _r;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (comp(R.second + 1, mid, w))
      r = mid - 1;
    else
      _r = mid, l = mid + 1;
  }
  if (!comp(R.first, _l, w) || comp(R.second + 1, _l, w))
    return make_pair(1, 0);
  if (!comp(R.first, _r, w) || comp(R.second + 1, _r, w))
    return make_pair(1, 0);
  return make_pair(_l, _r);
}
}  // namespace SA
namespace Multi {
pair<int, int> udat[N][20], ddat[N][20];
int fat[N][20], dep[N];
void dfs(int now, int fa, int c) {
  dep[now] = dep[fa] + 1;
  if (now != 1) udat[now][0] = ddat[now][0] = charInter[c];
  fat[now][0] = fa;
  for (int i = 1; (1 << i) < n; ++i) {
    fat[now][i] = fat[fat[now][i - 1]][i - 1];
    if (!fat[now][i]) break;
    udat[now][i] =
        SA::Merge(udat[now][i - 1], udat[fat[now][i - 1]][i - 1], (1 << i - 1));
    ddat[now][i] =
        SA::Merge(ddat[fat[now][i - 1]][i - 1], ddat[now][i - 1], (1 << i - 1));
  }
  for (auto e : Edge[now])
    if (e.first != fa) dfs(e.first, now, e.second);
}
int LCA(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = 19; ~i; --i)
    if (dep[fat[u][i]] >= dep[v]) u = fat[u][i];
  if (u == v) return u;
  for (int i = 19; ~i; --i)
    if (fat[u][i] != fat[v][i]) u = fat[u][i], v = fat[v][i];
  return fat[u][0];
}
pair<int, int> getInter(int u, int v) {
  int lca = LCA(u, v), w = 0;
  pair<int, int> res = make_pair(1, L), R = make_pair(1, L);
  for (int i = 19; ~i; --i)
    if (dep[fat[u][i]] >= dep[lca])
      res = SA::Merge(res, udat[u][i], w), w |= (1 << i), u = fat[u][i];
  for (int i = 19; ~i; --i)
    if (dep[fat[v][i]] >= dep[lca])
      R = SA::Merge(ddat[v][i], R, (1 << i)), v = fat[v][i];
  return SA::Merge(res, R, w);
}
}  // namespace Multi
vector<int> _add[N];
vector<pair<pair<int, int>, int> > _ask[N];
int Ans[N];
int c[N * 10];
int lb(int x) { return x & -x; }
void Add(int pos) {
  for (; pos <= L; pos += lb(pos)) ++c[pos];
}
int Ask(int pos) {
  int res = 0;
  for (; pos; pos -= lb(pos)) res += c[pos];
  return res;
}
void Work() {
  read(n), read(m), read(q);
  for (int i = 1; i < n; ++i) {
    int u, v;
    char c;
    read(u), read(v), scanf("%c", &c), c -= 'a' - 1;
    Edge[u].emplace_back(v, c), Edge[v].emplace_back(u, c);
  }
  for (int i = 1; i <= m; ++i) scanf("%s", str + 1), Insert(i, strlen(str + 1));
  SA::getSA();
  for (int i = 1; i <= L; ++i)
    if (bel[SA::sa[i]]) _add[bel[SA::sa[i]]].push_back(i);
  Multi::dfs(1, 0, 0);
  for (int i = 1; i <= q; ++i) {
    int u, v, l, r;
    read(u), read(v), read(l), read(r);
    pair<int, int> _ = Multi::getInter(u, v);
    if (_.first > _.second) continue;
    _ask[r].emplace_back(_, i);
    if (l > 1) _ask[l - 1].emplace_back(_, -i);
  }
  for (int i = 1; i <= m; ++i) {
    for (int p : _add[i]) Add(p);
    for (auto o : _ask[i]) {
      int res = Ask(o.first.second) - Ask(o.first.first - 1);
      if (o.second < 0)
        Ans[-o.second] -= res;
      else
        Ans[o.second] += res;
    }
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", Ans[i]);
}
int main() { Work(); }

### 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;
void read(int& x) {
  static char c;
  int f = 0;
  while (!isdigit(c = getchar()))
    if (c == '-') f = 1;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
  if (f) x = -x;
}
void chkmax(int& x, int y) {
  if (y > x) x = y;
}
void chkmin(int& x, int y) {
  if (y < x) x = y;
}
void chkmax(long long& x, long long y) {
  if (y > x) x = y;
}
void chkmin(long long& x, long long y) {
  if (y < x) x = y;
}
const int N = 2e5 + 10;
int n, m, q;
vector<pair<int, char> > Edge[N];
int L, bel[N];
char S[N], str[N];
void Insert(int pos, int len) {
  for (int i = 1; i <= len; ++i) S[++L] = str[i], bel[L] = pos;
  S[++L] = 'z' + 1;
}
pair<int, int> charInter[27];
namespace SA {
int sa[N], rk[N], id[N], px[N], oldrk[N * 2], height[N], Buc[N];
bool cmp(int x, int y, int w) {
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
void getSA() {
  int m = 300, p = 300;
  for (int i = 1; i <= L; ++i) ++Buc[rk[i] = S[i] - 'a' + 1];
  for (int i = 1; i <= m; ++i) Buc[i] += Buc[i - 1];
  for (int i = 1; i <= 26; ++i)
    charInter[i] = make_pair(Buc[i - 1] + 1, Buc[i]);
  for (int i = L; i; --i) sa[Buc[rk[i]]--] = i;
  for (int w = 1; w < L; w <<= 1) {
    for (int i = 1; i <= m; ++i) Buc[i] = 0;
    m = p, p = 0;
    for (int i = L; i > L - w; --i) id[++p] = i;
    for (int i = 1; i <= L; ++i)
      if (sa[i] > w) id[++p] = sa[i] - w;
    for (int i = 1; i <= L; ++i) ++Buc[px[i] = rk[id[i]]];
    for (int i = 1; i <= m; ++i) Buc[i] += Buc[i - 1];
    for (int i = L; i; --i) sa[Buc[px[i]]--] = id[i];
    memcpy(oldrk, rk, sizeof rk), p = 0;
    for (int i = 1; i <= L; ++i) rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
    if (p == L) {
      for (int i = 1; i <= L; ++i) sa[rk[i]] = i;
      break;
    }
  }
}
bool comp(int pos, int mid, int w) {
  if (sa[mid] + w > L) return false;
  return pos <= rk[sa[mid] + w];
}
pair<int, int> Merge(pair<int, int> L, pair<int, int> R, int w) {
  int _l = L.first, _r = L.second;
  int l, r, mid;
  l = _l, r = _r;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (comp(R.first, mid, w))
      r = mid - 1;
    else
      _l = mid, l = mid + 1;
  }
  if (!comp(R.first, _l, w)) ++_l;
  l = _l, r = _r;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (comp(R.second + 1, mid, w))
      r = mid - 1;
    else
      _r = mid, l = mid + 1;
  }
  if (!comp(R.first, _l, w) || comp(R.second + 1, _l, w))
    return make_pair(1, 0);
  if (!comp(R.first, _r, w) || comp(R.second + 1, _r, w))
    return make_pair(1, 0);
  return make_pair(_l, _r);
}
}  // namespace SA
namespace Multi {
pair<int, int> udat[N][20], ddat[N][20];
int fat[N][20], dep[N];
void dfs(int now, int fa, int c) {
  dep[now] = dep[fa] + 1;
  if (now != 1) udat[now][0] = ddat[now][0] = charInter[c];
  fat[now][0] = fa;
  for (int i = 1; (1 << i) < n; ++i) {
    fat[now][i] = fat[fat[now][i - 1]][i - 1];
    if (!fat[now][i]) break;
    udat[now][i] =
        SA::Merge(udat[now][i - 1], udat[fat[now][i - 1]][i - 1], (1 << i - 1));
    ddat[now][i] =
        SA::Merge(ddat[fat[now][i - 1]][i - 1], ddat[now][i - 1], (1 << i - 1));
  }
  for (auto e : Edge[now])
    if (e.first != fa) dfs(e.first, now, e.second);
}
int LCA(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = 19; ~i; --i)
    if (dep[fat[u][i]] >= dep[v]) u = fat[u][i];
  if (u == v) return u;
  for (int i = 19; ~i; --i)
    if (fat[u][i] != fat[v][i]) u = fat[u][i], v = fat[v][i];
  return fat[u][0];
}
pair<int, int> getInter(int u, int v) {
  int lca = LCA(u, v), w = 0;
  pair<int, int> res = make_pair(1, L), R = make_pair(1, L);
  for (int i = 19; ~i; --i)
    if (dep[fat[u][i]] >= dep[lca])
      res = SA::Merge(res, udat[u][i], w), w |= (1 << i), u = fat[u][i];
  for (int i = 19; ~i; --i)
    if (dep[fat[v][i]] >= dep[lca])
      R = SA::Merge(ddat[v][i], R, (1 << i)), v = fat[v][i];
  return SA::Merge(res, R, w);
}
}  // namespace Multi
vector<int> _add[N];
vector<pair<pair<int, int>, int> > _ask[N];
int Ans[N];
int c[N * 10];
int lb(int x) { return x & -x; }
void Add(int pos) {
  for (; pos <= L; pos += lb(pos)) ++c[pos];
}
int Ask(int pos) {
  int res = 0;
  for (; pos; pos -= lb(pos)) res += c[pos];
  return res;
}
void Work() {
  read(n), read(m), read(q);
  for (int i = 1; i < n; ++i) {
    int u, v;
    char c;
    read(u), read(v), scanf("%c", &c), c -= 'a' - 1;
    Edge[u].emplace_back(v, c), Edge[v].emplace_back(u, c);
  }
  for (int i = 1; i <= m; ++i) scanf("%s", str + 1), Insert(i, strlen(str + 1));
  SA::getSA();
  for (int i = 1; i <= L; ++i)
    if (bel[SA::sa[i]]) _add[bel[SA::sa[i]]].push_back(i);
  Multi::dfs(1, 0, 0);
  for (int i = 1; i <= q; ++i) {
    int u, v, l, r;
    read(u), read(v), read(l), read(r);
    pair<int, int> _ = Multi::getInter(u, v);
    if (_.first > _.second) continue;
    _ask[r].emplace_back(_, i);
    if (l > 1) _ask[l - 1].emplace_back(_, -i);
  }
  for (int i = 1; i <= m; ++i) {
    for (int p : _add[i]) Add(p);
    for (auto o : _ask[i]) {
      int res = Ask(o.first.second) - Ask(o.first.first - 1);
      if (o.second < 0)
        Ans[-o.second] -= res;
      else
        Ans[o.second] += res;
    }
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", Ans[i]);
}
int main() { Work(); }

```