#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int n, m, q, qu[100005], qv[100005], qs[100005], qr[100005];
vector<pair<int, char> > G[100005];
string T[100005];
int pos[100005];
vector<int> vs[100005], vr[100005];
struct SAM {
  int cnt, nxt[200005][26], tch[200005][26], par[200005], dep[200005];
  vector<int> G[200005];
  pair<int, int> vid[200005];
  int dfn[200005], dfo[200005], tot;
  void clear() {
    cnt = 1;
    memset(nxt, -1, sizeof(nxt));
    memset(par, -1, sizeof(par));
    memset(dep, 0, sizeof(dep));
  }
  int append(int x, int ch) {
    if (nxt[x][ch] != -1) return nxt[x][ch];
    int ret = cnt++;
    dep[ret] = dep[x] + 1;
    for (; x != -1 && nxt[x][ch] == -1; x = par[x]) nxt[x][ch] = ret;
    if (x == -1)
      par[ret] = 0;
    else if (dep[x] + 1 == dep[nxt[x][ch]])
      par[ret] = nxt[x][ch];
    else {
      int nr = cnt++, fr = nxt[x][ch];
      dep[nr] = dep[x] + 1;
      par[nr] = par[fr];
      par[fr] = nr;
      for (int i = 0; i < (int)(26); i++) nxt[nr][i] = nxt[fr][i];
      par[ret] = nr;
      for (; x != -1 && nxt[x][ch] == fr; x = par[x]) nxt[x][ch] = nr;
    }
    return ret;
  }
  void dfs(int v, int coef) {
    dfn[v] = ++tot;
    for (int i = 0; i < (int)(26); i++) tch[v][i] = -1;
    for (int i = 0; i < (int)(G[v].size()); i++) {
      dfs(G[v][i], coef);
      vid[v] = vid[G[v][i]];
      tch[v][T[vid[v].first][vid[v].second + coef * dep[v]]] = G[v][i];
    }
    dfo[v] = tot;
  }
  void getre(int coef) {
    for (int i = 1; i <= (int)(cnt - 1); i++) G[par[i]].push_back(i);
    dfs(0, coef);
  }
} S, R;
pair<int, int> gnxtS(pair<int, int> cur, int ch, const SAM& X, int coef) {
  if (cur.first == -1) return make_pair(-1, cur.second + 1);
  if (X.dep[cur.first] == cur.second)
    return make_pair(X.tch[cur.first][ch], cur.second + 1);
  else
    return make_pair(T[X.vid[cur.first].first]
                      [X.vid[cur.first].second + coef * cur.second] == ch
                         ? cur.first
                         : -1,
                     cur.second + 1);
}
queue<int> que;
void gen_sam(SAM& cur, vector<int> ver[]) {
  cur.clear();
  for (int i = 0; i < (int)(m); i++) {
    pos[i] = 0;
    ver[i].push_back(0);
    que.push(i);
  }
  while (!que.empty()) {
    int id = que.front();
    que.pop();
    int cv = ver[id].back();
    ver[id].push_back(cur.append(cv, T[id][pos[id]++]));
    if (pos[id] < (int)T[id].length()) que.push(id);
  }
}
bool del[100005];
int siz[100005], cid[100005];
pair<int, int> ps[100005], pr[100005];
vector<int> hv[100005];
void dfs0(int v, int p) {
  siz[v] = 1;
  for (int i = 0; i < (int)(G[v].size()); i++) {
    int u = G[v][i].first;
    if (del[u] || u == p) continue;
    dfs0(u, v);
    siz[v] += siz[u];
  }
}
int dfs1(int v, int p, int tsz) {
  for (int i = 0; i < (int)(G[v].size()); i++) {
    int u = G[v][i].first;
    if (del[u] || u == p) continue;
    if (siz[u] * 2 > tsz) return dfs1(u, v, tsz);
  }
  return v;
}
void dfs2(int v, int p, int gr) {
  cid[v] = gr;
  for (int i = 0; i < (int)(G[v].size()); i++) {
    int u = G[v][i].first;
    if (del[u] || u == p) continue;
    ps[u] = gnxtS(ps[v], G[v][i].second, S, -1);
    pr[u] = gnxtS(pr[v], G[v][i].second, R, 1);
    dfs2(u, v, gr ? gr : u);
  }
}
void solve(int v) {
  dfs0(v, 0);
  int u = dfs1(v, 0, siz[v]);
  swap(hv[u], hv[v]);
  ps[u] = pr[u] = make_pair(0, 0);
  dfs2(u, 0, 0);
  for (int i = 0; i < (int)(hv[u].size()); i++) {
    int cq = hv[u][i];
    if (cid[qu[cq]] && cid[qv[cq]] && cid[qu[cq]] == cid[qv[cq]])
      hv[cid[qu[cq]]].push_back(cq);
    else {
      qs[cq] = ps[qu[cq]].first;
      qr[cq] = pr[qv[cq]].first;
    }
  }
  del[u] = true;
  for (int i = 0; i < (int)(G[u].size()); i++) {
    v = G[u][i].first;
    if (!del[v]) solve(v);
  }
}
struct fwt {
  int dat[262145];
  void add(int id, int val) {
    for (id++; id > 0; id -= id & -id) dat[id] += val;
  }
  int query(int id) {
    int ret = 0;
    for (id++; id <= 262144; id += id & -id) ret += dat[id];
    return ret;
  }
  int query(int l, int r) { return query(l) - query(r + 1); }
} tre;
int ans[100005];
vector<pair<int, int> > qy[100005];
vector<pair<int, pair<int, int> > > calc(int l, int r) {
  if (l == r) {
    vector<pair<int, pair<int, int> > > ret;
    for (int i = 0; i < (int)(vs[l].size()); i++)
      ret.push_back(make_pair(S.dfn[vs[l][i]], make_pair(0, R.dfn[vr[l][i]])));
    for (int i = 0; i < (int)(qy[l].size()); i++) {
      int cq = qy[l][i].first;
      if (qy[l][i].second == -1) {
        ret.push_back(make_pair(S.dfn[qs[cq]] - 1, make_pair(1, cq)));
        ret.push_back(make_pair(S.dfo[qs[cq]] + 1, make_pair(-1, cq)));
      } else {
        ret.push_back(make_pair(S.dfn[qs[cq]], make_pair(-1, cq)));
        ret.push_back(make_pair(S.dfo[qs[cq]], make_pair(1, cq)));
      }
    }
    sort(ret.begin(), ret.end());
    return ret;
  }
  int mid = (l + r) >> 1;
  vector<pair<int, pair<int, int> > > A = calc(l, mid), B = calc(mid + 1, r), C;
  C.resize(A.size() + B.size());
  int i = 0, j = 0, k = 0;
  while (i < A.size() || j < B.size()) {
    pair<int, pair<int, int> > cur;
    if (j == B.size() || (i < A.size() && A[i] < B[j])) {
      C[k++] = cur = A[i++];
      if (cur.second.first == 0) tre.add(cur.second.second, 1);
    } else {
      C[k++] = cur = B[j++];
      if (cur.second.first != 0) {
        int cq = cur.second.second, cc = cur.second.first;
        ans[cq] += cc * tre.query(R.dfn[qr[cq]], R.dfo[qr[cq]]);
      }
    }
  }
  for (int i = 0; i < (int)(C.size()); i++)
    if (C[i].second.first == 0) tre.add(C[i].second.second, -1);
  return C;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m >> q;
  for (int i = 0; i < (int)(n - 1); i++) {
    int u, v;
    char c;
    cin >> u >> v >> c;
    c -= 'a';
    G[u].push_back(make_pair(v, c));
    G[v].push_back(make_pair(u, c));
  }
  for (int i = 0; i < (int)(m); i++) cin >> T[i];
  for (int i = 0; i < (int)(m); i++)
    for (int j = 0; j < (int)(T[i].size()); j++) T[i][j] -= 'a';
  for (int i = 0; i < (int)(q); i++) {
    int l, r;
    cin >> qu[i] >> qv[i] >> l >> r;
    qy[l - 1].push_back(make_pair(i, -1));
    qy[r].push_back(make_pair(i, 1));
  }
  gen_sam(S, vs);
  for (int i = 0; i < (int)(m); i++) reverse(T[i].begin(), T[i].end());
  gen_sam(R, vr);
  for (int i = 0; i < (int)(m); i++) {
    reverse(T[i].begin(), T[i].end());
    reverse(vr[i].begin(), vr[i].end());
  }
  for (int i = 0; i < (int)(m); i++)
    for (int j = 0; j < (int)(T[i].length()); j++)
      S.vid[vs[i][j + 1]] = R.vid[vr[i][j]] = make_pair(i, j);
  S.getre(-1);
  R.getre(1);
  for (int i = 0; i < (int)(q); i++) hv[1].push_back(i);
  solve(1);
  calc(0, m);
  for (int i = 0; i < (int)(q); i++) cout << ans[i] << '\n';
  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;
const int MOD = 998244353;
int n, m, q, qu[100005], qv[100005], qs[100005], qr[100005];
vector<pair<int, char> > G[100005];
string T[100005];
int pos[100005];
vector<int> vs[100005], vr[100005];
struct SAM {
  int cnt, nxt[200005][26], tch[200005][26], par[200005], dep[200005];
  vector<int> G[200005];
  pair<int, int> vid[200005];
  int dfn[200005], dfo[200005], tot;
  void clear() {
    cnt = 1;
    memset(nxt, -1, sizeof(nxt));
    memset(par, -1, sizeof(par));
    memset(dep, 0, sizeof(dep));
  }
  int append(int x, int ch) {
    if (nxt[x][ch] != -1) return nxt[x][ch];
    int ret = cnt++;
    dep[ret] = dep[x] + 1;
    for (; x != -1 && nxt[x][ch] == -1; x = par[x]) nxt[x][ch] = ret;
    if (x == -1)
      par[ret] = 0;
    else if (dep[x] + 1 == dep[nxt[x][ch]])
      par[ret] = nxt[x][ch];
    else {
      int nr = cnt++, fr = nxt[x][ch];
      dep[nr] = dep[x] + 1;
      par[nr] = par[fr];
      par[fr] = nr;
      for (int i = 0; i < (int)(26); i++) nxt[nr][i] = nxt[fr][i];
      par[ret] = nr;
      for (; x != -1 && nxt[x][ch] == fr; x = par[x]) nxt[x][ch] = nr;
    }
    return ret;
  }
  void dfs(int v, int coef) {
    dfn[v] = ++tot;
    for (int i = 0; i < (int)(26); i++) tch[v][i] = -1;
    for (int i = 0; i < (int)(G[v].size()); i++) {
      dfs(G[v][i], coef);
      vid[v] = vid[G[v][i]];
      tch[v][T[vid[v].first][vid[v].second + coef * dep[v]]] = G[v][i];
    }
    dfo[v] = tot;
  }
  void getre(int coef) {
    for (int i = 1; i <= (int)(cnt - 1); i++) G[par[i]].push_back(i);
    dfs(0, coef);
  }
} S, R;
pair<int, int> gnxtS(pair<int, int> cur, int ch, const SAM& X, int coef) {
  if (cur.first == -1) return make_pair(-1, cur.second + 1);
  if (X.dep[cur.first] == cur.second)
    return make_pair(X.tch[cur.first][ch], cur.second + 1);
  else
    return make_pair(T[X.vid[cur.first].first]
                      [X.vid[cur.first].second + coef * cur.second] == ch
                         ? cur.first
                         : -1,
                     cur.second + 1);
}
queue<int> que;
void gen_sam(SAM& cur, vector<int> ver[]) {
  cur.clear();
  for (int i = 0; i < (int)(m); i++) {
    pos[i] = 0;
    ver[i].push_back(0);
    que.push(i);
  }
  while (!que.empty()) {
    int id = que.front();
    que.pop();
    int cv = ver[id].back();
    ver[id].push_back(cur.append(cv, T[id][pos[id]++]));
    if (pos[id] < (int)T[id].length()) que.push(id);
  }
}
bool del[100005];
int siz[100005], cid[100005];
pair<int, int> ps[100005], pr[100005];
vector<int> hv[100005];
void dfs0(int v, int p) {
  siz[v] = 1;
  for (int i = 0; i < (int)(G[v].size()); i++) {
    int u = G[v][i].first;
    if (del[u] || u == p) continue;
    dfs0(u, v);
    siz[v] += siz[u];
  }
}
int dfs1(int v, int p, int tsz) {
  for (int i = 0; i < (int)(G[v].size()); i++) {
    int u = G[v][i].first;
    if (del[u] || u == p) continue;
    if (siz[u] * 2 > tsz) return dfs1(u, v, tsz);
  }
  return v;
}
void dfs2(int v, int p, int gr) {
  cid[v] = gr;
  for (int i = 0; i < (int)(G[v].size()); i++) {
    int u = G[v][i].first;
    if (del[u] || u == p) continue;
    ps[u] = gnxtS(ps[v], G[v][i].second, S, -1);
    pr[u] = gnxtS(pr[v], G[v][i].second, R, 1);
    dfs2(u, v, gr ? gr : u);
  }
}
void solve(int v) {
  dfs0(v, 0);
  int u = dfs1(v, 0, siz[v]);
  swap(hv[u], hv[v]);
  ps[u] = pr[u] = make_pair(0, 0);
  dfs2(u, 0, 0);
  for (int i = 0; i < (int)(hv[u].size()); i++) {
    int cq = hv[u][i];
    if (cid[qu[cq]] && cid[qv[cq]] && cid[qu[cq]] == cid[qv[cq]])
      hv[cid[qu[cq]]].push_back(cq);
    else {
      qs[cq] = ps[qu[cq]].first;
      qr[cq] = pr[qv[cq]].first;
    }
  }
  del[u] = true;
  for (int i = 0; i < (int)(G[u].size()); i++) {
    v = G[u][i].first;
    if (!del[v]) solve(v);
  }
}
struct fwt {
  int dat[262145];
  void add(int id, int val) {
    for (id++; id > 0; id -= id & -id) dat[id] += val;
  }
  int query(int id) {
    int ret = 0;
    for (id++; id <= 262144; id += id & -id) ret += dat[id];
    return ret;
  }
  int query(int l, int r) { return query(l) - query(r + 1); }
} tre;
int ans[100005];
vector<pair<int, int> > qy[100005];
vector<pair<int, pair<int, int> > > calc(int l, int r) {
  if (l == r) {
    vector<pair<int, pair<int, int> > > ret;
    for (int i = 0; i < (int)(vs[l].size()); i++)
      ret.push_back(make_pair(S.dfn[vs[l][i]], make_pair(0, R.dfn[vr[l][i]])));
    for (int i = 0; i < (int)(qy[l].size()); i++) {
      int cq = qy[l][i].first;
      if (qy[l][i].second == -1) {
        ret.push_back(make_pair(S.dfn[qs[cq]] - 1, make_pair(1, cq)));
        ret.push_back(make_pair(S.dfo[qs[cq]] + 1, make_pair(-1, cq)));
      } else {
        ret.push_back(make_pair(S.dfn[qs[cq]], make_pair(-1, cq)));
        ret.push_back(make_pair(S.dfo[qs[cq]], make_pair(1, cq)));
      }
    }
    sort(ret.begin(), ret.end());
    return ret;
  }
  int mid = (l + r) >> 1;
  vector<pair<int, pair<int, int> > > A = calc(l, mid), B = calc(mid + 1, r), C;
  C.resize(A.size() + B.size());
  int i = 0, j = 0, k = 0;
  while (i < A.size() || j < B.size()) {
    pair<int, pair<int, int> > cur;
    if (j == B.size() || (i < A.size() && A[i] < B[j])) {
      C[k++] = cur = A[i++];
      if (cur.second.first == 0) tre.add(cur.second.second, 1);
    } else {
      C[k++] = cur = B[j++];
      if (cur.second.first != 0) {
        int cq = cur.second.second, cc = cur.second.first;
        ans[cq] += cc * tre.query(R.dfn[qr[cq]], R.dfo[qr[cq]]);
      }
    }
  }
  for (int i = 0; i < (int)(C.size()); i++)
    if (C[i].second.first == 0) tre.add(C[i].second.second, -1);
  return C;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m >> q;
  for (int i = 0; i < (int)(n - 1); i++) {
    int u, v;
    char c;
    cin >> u >> v >> c;
    c -= 'a';
    G[u].push_back(make_pair(v, c));
    G[v].push_back(make_pair(u, c));
  }
  for (int i = 0; i < (int)(m); i++) cin >> T[i];
  for (int i = 0; i < (int)(m); i++)
    for (int j = 0; j < (int)(T[i].size()); j++) T[i][j] -= 'a';
  for (int i = 0; i < (int)(q); i++) {
    int l, r;
    cin >> qu[i] >> qv[i] >> l >> r;
    qy[l - 1].push_back(make_pair(i, -1));
    qy[r].push_back(make_pair(i, 1));
  }
  gen_sam(S, vs);
  for (int i = 0; i < (int)(m); i++) reverse(T[i].begin(), T[i].end());
  gen_sam(R, vr);
  for (int i = 0; i < (int)(m); i++) {
    reverse(T[i].begin(), T[i].end());
    reverse(vr[i].begin(), vr[i].end());
  }
  for (int i = 0; i < (int)(m); i++)
    for (int j = 0; j < (int)(T[i].length()); j++)
      S.vid[vs[i][j + 1]] = R.vid[vr[i][j]] = make_pair(i, j);
  S.getre(-1);
  R.getre(1);
  for (int i = 0; i < (int)(q); i++) hv[1].push_back(i);
  solve(1);
  calc(0, m);
  for (int i = 0; i < (int)(q); i++) cout << ans[i] << '\n';
  return 0;
}

```