#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10, L = 19;
vector<pair<int, char>> to[N];
string str[N];
int pos[N];
int n, m, q;
char s[N];
int from[N];
int sa[N], rk[N], tp[N], bkt[N], hei[N], len, st[L][N], l2[N];
int p0[N];
bool cmp(int x, int y, int t) {
  return tp[x] == tp[y] && tp[x + t] == tp[y + t];
}
void tros(int len, int m) {
  for (int i = 1; i <= m; i++) bkt[i] = 0;
  for (int i = 1; i <= len; i++) bkt[rk[tp[i]]]++;
  for (int i = 1; i <= m; i++) bkt[i] += bkt[i - 1];
  for (int i = len; i >= 1; i--) sa[bkt[rk[tp[i]]]--] = tp[i];
}
void get_sa() {
  len = strlen(s + 1);
  int m = 128;
  for (int i = 1; i <= len; i++) tp[i] = i, rk[i] = s[i];
  tros(len, m);
  for (int l = 1, p = 0; p < len; m = p, l <<= 1) {
    p = 0;
    for (int i = len - l + 1; i <= len; i++) tp[++p] = i;
    for (int i = 1; i <= len; i++)
      if (sa[i] > l) tp[++p] = sa[i] - l;
    tros(len, m);
    memcpy(tp, rk, sizeof(tp));
    rk[sa[1]] = p = 1;
    for (int i = 2; i <= len; i++)
      rk[sa[i]] = cmp(sa[i], sa[i - 1], l) ? p : ++p;
  }
  for (int i = 1, t = 0; i <= len; i++) {
    if (t) --t;
    while (s[i + t] == s[sa[rk[i] - 1] + t]) ++t;
    hei[rk[i]] = t;
  }
  for (int i = 1; i <= len; i++) st[0][i] = hei[i];
  for (int i = 1; i < L; i++) {
    for (int j = 1; j <= len - (1 << (i - 1)); j++)
      st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
  }
  for (int i = 2; i <= len; i++) l2[i] = l2[i >> 1] + 1;
}
int qmin(int x, int y) {
  int t = l2[y - x + 1];
  return min(st[t][x], st[t][y - (1 << t) + 1]);
}
int lcp(int x, int y) {
  if (x == y) return len - x + 1;
  x = rk[x], y = rk[y];
  if (x > y) swap(x, y);
  return qmin(x + 1, y);
}
int sz[N], mxch[N], top[N], dep[N], fa[N];
void ss0(int x) {
  sz[x] = 1;
  for (auto &i : to[x]) {
    int v = i.first;
    if (v == fa[x]) continue;
    fa[v] = x;
    dep[v] = dep[x] + 1;
    ss0(v);
    sz[x] += sz[v];
    if (sz[v] > sz[mxch[x]]) mxch[x] = v;
  }
  if (mxch[x])
    for (auto &i : to[x])
      if (i.first == mxch[x]) swap(i, to[x][0]);
}
int dfn[N], dfnn, dpos[N], upos[N];
void ss1(int x, int t) {
  top[x] = t;
  dfn[x] = ++dfnn;
  bool first = 1;
  for (auto &i : to[x]) {
    int v = i.first;
    if (v == fa[x]) continue;
    ++len;
    s[len] = i.second;
    from[len] = m + 1;
    dpos[v] = len;
    ss1(v, first ? t : v);
    first = 0;
  }
}
void ss2(int x) {
  for (int I = to[x].size() - 1; I >= 0; I--) {
    auto &i = to[x][I];
    int v = i.first;
    if (v == fa[x]) continue;
    ss2(v);
    ++len;
    s[len] = i.second;
    from[len] = m + 2;
    upos[v] = len;
  }
}
vector<pair<int, int>> get_intervals(int u, int v) {
  vector<pair<int, int>> v1, v2;
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) {
      v2.push_back({dpos[top[v]], dpos[v]});
      v = fa[top[v]];
    } else {
      v1.push_back({upos[u], upos[top[u]]});
      u = fa[top[u]];
    }
  }
  if (dep[u] != dep[v]) {
    if (dep[u] > dep[v])
      v1.push_back({upos[u], upos[mxch[v]]});
    else
      v2.push_back({dpos[mxch[u]], dpos[v]});
  }
  reverse(v2.begin(), v2.end());
  for (auto &i : v2) v1.push_back(i);
  return v1;
}
int lcp(int x, vector<pair<int, int>> &y) {
  int ans = 0;
  for (auto &i : y) {
    int l = i.first, r = i.second;
    int t = lcp(x, l);
    t = min(t, r - l + 1);
    ans += t;
    if (t < r - l + 1) break;
    x += t;
  }
  return ans;
}
bool cmp1(int x, const vector<pair<int, int>> &y) {
  for (auto &i : y) {
    int l = i.first, r = i.second;
    int t = lcp(x, l);
    t = min(t, r - l + 1);
    if (t < r - l + 1) return s[x + t] < s[l + t];
    x += t;
  }
  return 0;
}
bool cmp2(const vector<pair<int, int>> &y, int x) {
  for (auto &i : y) {
    int l = i.first, r = i.second;
    int t = lcp(x, l);
    t = min(t, r - l + 1);
    if (t < r - l + 1) return s[l + t] < s[x + t];
    x += t;
  }
  return 0;
}
int qu[N], qv[N], ql[N], qr[N], qL[N], qR[N], ans[N];
vector<tuple<int, int, int>> que[N];
int t[N];
void mdf(int p, int v) {
  for (; p <= m + 2; p += p & -p) t[p] += v;
}
int qry(int p) {
  int r = 0;
  for (; p; p -= p & -p) r += t[p];
  return r;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> q;
  for (int i = 1; i < n; i++) {
    int x, y;
    char c;
    cin >> x >> y >> c;
    to[x].push_back({y, c});
    to[y].push_back({x, c});
  }
  for (int i = 1; i <= m; i++) cin >> str[i];
  pos[1] = 1;
  for (int i = 1; i <= m; i++) {
    for (int j = 0; j < str[i].size(); j++)
      s[pos[i] + j] = str[i][j], from[pos[i] + j] = i;
    s[pos[i] + str[i].size()] = '$';
    from[pos[i] + str[i].size()] = i;
    pos[i + 1] = pos[i] + str[i].size() + 1;
  }
  len = pos[m + 1] - 1;
  ss0(1);
  ss1(1, 1);
  ss2(1);
  get_sa();
  for (int i = 1; i <= q; i++) {
    cin >> qu[i] >> qv[i] >> ql[i] >> qr[i];
    auto v = get_intervals(qu[i], qv[i]);
    qL[i] = lower_bound(sa + 1, sa + len + 1, v, cmp1) - sa;
    qR[i] = upper_bound(sa + 1, sa + len + 1, v, cmp2) - sa - 1;
  }
  for (int i = 1; i <= q; i++) {
    que[qL[i] - 1].emplace_back(ql[i] - 1, 1, i);
    que[qL[i] - 1].emplace_back(qr[i], -1, i);
    que[qR[i]].emplace_back(ql[i] - 1, -1, i);
    que[qR[i]].emplace_back(qr[i], 1, i);
  }
  for (int i = 1; i <= len; i++) {
    mdf(from[sa[i]], 1);
    for (auto j : que[i]) {
      int x = get<0>(j), y = get<1>(j), z = get<2>(j);
      ans[z] += y * qry(x);
    }
  }
  for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 = 4e5 + 10, L = 19;
vector<pair<int, char>> to[N];
string str[N];
int pos[N];
int n, m, q;
char s[N];
int from[N];
int sa[N], rk[N], tp[N], bkt[N], hei[N], len, st[L][N], l2[N];
int p0[N];
bool cmp(int x, int y, int t) {
  return tp[x] == tp[y] && tp[x + t] == tp[y + t];
}
void tros(int len, int m) {
  for (int i = 1; i <= m; i++) bkt[i] = 0;
  for (int i = 1; i <= len; i++) bkt[rk[tp[i]]]++;
  for (int i = 1; i <= m; i++) bkt[i] += bkt[i - 1];
  for (int i = len; i >= 1; i--) sa[bkt[rk[tp[i]]]--] = tp[i];
}
void get_sa() {
  len = strlen(s + 1);
  int m = 128;
  for (int i = 1; i <= len; i++) tp[i] = i, rk[i] = s[i];
  tros(len, m);
  for (int l = 1, p = 0; p < len; m = p, l <<= 1) {
    p = 0;
    for (int i = len - l + 1; i <= len; i++) tp[++p] = i;
    for (int i = 1; i <= len; i++)
      if (sa[i] > l) tp[++p] = sa[i] - l;
    tros(len, m);
    memcpy(tp, rk, sizeof(tp));
    rk[sa[1]] = p = 1;
    for (int i = 2; i <= len; i++)
      rk[sa[i]] = cmp(sa[i], sa[i - 1], l) ? p : ++p;
  }
  for (int i = 1, t = 0; i <= len; i++) {
    if (t) --t;
    while (s[i + t] == s[sa[rk[i] - 1] + t]) ++t;
    hei[rk[i]] = t;
  }
  for (int i = 1; i <= len; i++) st[0][i] = hei[i];
  for (int i = 1; i < L; i++) {
    for (int j = 1; j <= len - (1 << (i - 1)); j++)
      st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
  }
  for (int i = 2; i <= len; i++) l2[i] = l2[i >> 1] + 1;
}
int qmin(int x, int y) {
  int t = l2[y - x + 1];
  return min(st[t][x], st[t][y - (1 << t) + 1]);
}
int lcp(int x, int y) {
  if (x == y) return len - x + 1;
  x = rk[x], y = rk[y];
  if (x > y) swap(x, y);
  return qmin(x + 1, y);
}
int sz[N], mxch[N], top[N], dep[N], fa[N];
void ss0(int x) {
  sz[x] = 1;
  for (auto &i : to[x]) {
    int v = i.first;
    if (v == fa[x]) continue;
    fa[v] = x;
    dep[v] = dep[x] + 1;
    ss0(v);
    sz[x] += sz[v];
    if (sz[v] > sz[mxch[x]]) mxch[x] = v;
  }
  if (mxch[x])
    for (auto &i : to[x])
      if (i.first == mxch[x]) swap(i, to[x][0]);
}
int dfn[N], dfnn, dpos[N], upos[N];
void ss1(int x, int t) {
  top[x] = t;
  dfn[x] = ++dfnn;
  bool first = 1;
  for (auto &i : to[x]) {
    int v = i.first;
    if (v == fa[x]) continue;
    ++len;
    s[len] = i.second;
    from[len] = m + 1;
    dpos[v] = len;
    ss1(v, first ? t : v);
    first = 0;
  }
}
void ss2(int x) {
  for (int I = to[x].size() - 1; I >= 0; I--) {
    auto &i = to[x][I];
    int v = i.first;
    if (v == fa[x]) continue;
    ss2(v);
    ++len;
    s[len] = i.second;
    from[len] = m + 2;
    upos[v] = len;
  }
}
vector<pair<int, int>> get_intervals(int u, int v) {
  vector<pair<int, int>> v1, v2;
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) {
      v2.push_back({dpos[top[v]], dpos[v]});
      v = fa[top[v]];
    } else {
      v1.push_back({upos[u], upos[top[u]]});
      u = fa[top[u]];
    }
  }
  if (dep[u] != dep[v]) {
    if (dep[u] > dep[v])
      v1.push_back({upos[u], upos[mxch[v]]});
    else
      v2.push_back({dpos[mxch[u]], dpos[v]});
  }
  reverse(v2.begin(), v2.end());
  for (auto &i : v2) v1.push_back(i);
  return v1;
}
int lcp(int x, vector<pair<int, int>> &y) {
  int ans = 0;
  for (auto &i : y) {
    int l = i.first, r = i.second;
    int t = lcp(x, l);
    t = min(t, r - l + 1);
    ans += t;
    if (t < r - l + 1) break;
    x += t;
  }
  return ans;
}
bool cmp1(int x, const vector<pair<int, int>> &y) {
  for (auto &i : y) {
    int l = i.first, r = i.second;
    int t = lcp(x, l);
    t = min(t, r - l + 1);
    if (t < r - l + 1) return s[x + t] < s[l + t];
    x += t;
  }
  return 0;
}
bool cmp2(const vector<pair<int, int>> &y, int x) {
  for (auto &i : y) {
    int l = i.first, r = i.second;
    int t = lcp(x, l);
    t = min(t, r - l + 1);
    if (t < r - l + 1) return s[l + t] < s[x + t];
    x += t;
  }
  return 0;
}
int qu[N], qv[N], ql[N], qr[N], qL[N], qR[N], ans[N];
vector<tuple<int, int, int>> que[N];
int t[N];
void mdf(int p, int v) {
  for (; p <= m + 2; p += p & -p) t[p] += v;
}
int qry(int p) {
  int r = 0;
  for (; p; p -= p & -p) r += t[p];
  return r;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> q;
  for (int i = 1; i < n; i++) {
    int x, y;
    char c;
    cin >> x >> y >> c;
    to[x].push_back({y, c});
    to[y].push_back({x, c});
  }
  for (int i = 1; i <= m; i++) cin >> str[i];
  pos[1] = 1;
  for (int i = 1; i <= m; i++) {
    for (int j = 0; j < str[i].size(); j++)
      s[pos[i] + j] = str[i][j], from[pos[i] + j] = i;
    s[pos[i] + str[i].size()] = '$';
    from[pos[i] + str[i].size()] = i;
    pos[i + 1] = pos[i] + str[i].size() + 1;
  }
  len = pos[m + 1] - 1;
  ss0(1);
  ss1(1, 1);
  ss2(1);
  get_sa();
  for (int i = 1; i <= q; i++) {
    cin >> qu[i] >> qv[i] >> ql[i] >> qr[i];
    auto v = get_intervals(qu[i], qv[i]);
    qL[i] = lower_bound(sa + 1, sa + len + 1, v, cmp1) - sa;
    qR[i] = upper_bound(sa + 1, sa + len + 1, v, cmp2) - sa - 1;
  }
  for (int i = 1; i <= q; i++) {
    que[qL[i] - 1].emplace_back(ql[i] - 1, 1, i);
    que[qL[i] - 1].emplace_back(qr[i], -1, i);
    que[qR[i]].emplace_back(ql[i] - 1, -1, i);
    que[qR[i]].emplace_back(qr[i], 1, i);
  }
  for (int i = 1; i <= len; i++) {
    mdf(from[sa[i]], 1);
    for (auto j : que[i]) {
      int x = get<0>(j), y = get<1>(j), z = get<2>(j);
      ans[z] += y * qry(x);
    }
  }
  for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

```