#include <bits/stdc++.h>
using std::pair;
using std::vector;
const int N = 200005;
int n, m, q, x[N], y[N];
int s[N];
int posl[N], posr[N], sa[N], rk[N], id[N], cnt[N], rid[N], dep[N], top;
int al[N], ar[N], rans[N];
int sum[N], tot;
vector<pair<int, int> > e[N];
vector<int> qr[N];
inline void add(int p, int v) {
  while (p <= tot) sum[p] += v, p += p & (-p);
}
inline int ask(int p) {
  int ret = 0;
  while (p) ret += sum[p], p -= p & (-p);
  return ret;
}
void SA(int n) {
  for (int i = 1; i <= n; ++i) ++cnt[s[i]];
  int m = 27;
  for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (int i = 1; i <= n; ++i) sa[cnt[rk[i] = s[i]]--] = i;
  for (int len = 1; len == 1 || m != n; len <<= 1) {
    top = 0;
    for (int i = n - len + 1; i <= n; ++i) id[++top] = i;
    for (int i = 1; i <= n; ++i)
      if (sa[i] > len) id[++top] = sa[i] - len;
    std::fill(cnt, cnt + m + 1, 0);
    for (int i = 1; i <= n; ++i) ++cnt[rk[i]], rid[i] = rk[id[i]];
    for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (int i = top; i; --i) sa[cnt[rid[i]]--] = id[i];
    std::copy(rk + 1, rk + n + 1, rid + 1);
    auto cmp = [&](int x, int y) {
      return rid[x] == rid[y] && (x + len > n ? 0 : rid[x + len]) ==
                                     (y + len > n ? 0 : rid[y + len]);
    };
    m = 0;
    for (int i = 1; i <= n; ++i) {
      if (i == 1 || !cmp(sa[i - 1], sa[i])) ++m;
      rk[sa[i]] = m;
    }
  }
}
int ul[N][20], ur[N][20], dl[N][20], dr[N][20], pa[N][20];
inline bool cmple(int xl, int xr, int y, int p, int len) {
  return (xl <= rk[p] && rk[p] <= xr) ? y <= (p + len > tot ? 0 : rk[p + len])
                                      : xl < rk[p];
}
inline void merge(int xl, int xr, int yl, int yr, int len, int &x, int &y) {
  int l = 0, r = tot;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (cmple(xl, xr, yl, sa[mid], len))
      r = mid - 1;
    else
      l = mid;
  }
  x = l + 1;
  r = tot;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (cmple(xl, xr, yr + 1, sa[mid], len))
      r = mid - 1;
    else
      l = mid;
  }
  y = l;
}
void dfs(int u, int fa, int w) {
  pa[u][0] = fa;
  dep[u] = dep[fa] + 1;
  ul[u][0] = dl[u][0] = al[w], ur[u][0] = dr[u][0] = ar[w];
  for (int i = 1; (1 << i) <= n; ++i) {
    pa[u][i] = pa[pa[u][i - 1]][i - 1];
    if (!pa[u][i]) break;
    merge(ul[u][i - 1], ur[u][i - 1], ul[pa[u][i - 1]][i - 1],
          ur[pa[u][i - 1]][i - 1], (1 << (i - 1)), ul[u][i], ur[u][i]);
    int len = 1 << (i - 1);
    merge(dl[pa[u][i - 1]][i - 1], dr[pa[u][i - 1]][i - 1], dl[u][i - 1],
          dr[u][i - 1], len, dl[u][i], dr[u][i]);
  }
  for (auto [v, c] : e[u])
    if (v != fa) {
      dfs(v, u, c);
    }
}
inline int lca(int x, int y) {
  if (dep[x] < dep[y]) std::swap(x, y);
  for (int i = 19; ~i; --i)
    if (dep[pa[x][i]] >= dep[y]) x = pa[x][i];
  if (x == y) return x;
  for (int i = 19; ~i; --i)
    if (pa[x][i] != pa[y][i]) x = pa[x][i], y = pa[y][i];
  return pa[x][0];
}
void find(int x, int y, int &cl, int &cr) {
  int l = lca(x, y);
  int xl = 0, xr = tot, yl = 0, yr = tot;
  int cur = 0;
  for (int i = 19; ~i; --i)
    if (dep[pa[x][i]] >= dep[l]) {
      merge(xl, xr, ul[x][i], ur[x][i], cur, xl, xr);
      cur |= (1 << i);
      x = pa[x][i];
    }
  for (int i = 19; ~i; --i)
    if (dep[pa[y][i]] >= dep[l]) {
      merge(dl[y][i], dr[y][i], yl, yr, 1 << i, yl, yr);
      y = pa[y][i];
    }
  merge(xl, xr, yl, yr, cur, cl, cr);
}
char t[N];
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1, x, y; i < n; ++i) {
    scanf("%d%d%s", &x, &y, t);
    e[x].push_back({y, t[0] - 'a' + 1});
    e[y].push_back({x, t[0] - 'a' + 1});
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%s", t + 1);
    int len = strlen(t + 1);
    for (int i = 1; i <= len; ++i) s[tot + i] = t[i] - 'a' + 1;
    posl[i] = tot + 1, posr[i] = tot + len;
    s[tot + len + 1] = 27;
    tot += len + 1;
  }
  SA(tot);
  for (int i = 0; i <= 19; ++i) ur[0][i] = dr[0][i] = tot;
  ar[0] = tot;
  std::fill(al + 1, al + 27 + 1, tot + 1);
  for (int i = 1; i <= tot; ++i)
    if (s[i] <= 26) {
      al[s[i]] = std::min(al[s[i]], rk[i]);
      ar[s[i]] = std::max(ar[s[i]], rk[i]);
    }
  dfs(1, 0, 0);
  for (int i = 1, l, r; i <= q; ++i) {
    scanf("%d%d%d%d", x + i, y + i, &l, &r);
    qr[l - 1].push_back(-i);
    qr[r].push_back(i);
  }
  for (int i = 1; i <= m; ++i) {
    int l, r;
    for (int j = posl[i]; j <= posr[i]; ++j) add(rk[j], 1);
    for (int _x : qr[i]) {
      int x = std::abs(_x);
      find(::x[x], y[x], l, r);
      int v = ask(r) - ask(l - 1);
      if (_x < 0)
        rans[x] -= v;
      else
        rans[x] += v;
    }
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", rans[i]);
  return 0;
}

### Prompt

In Cpp, your task is to solve 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 std::pair;
using std::vector;
const int N = 200005;
int n, m, q, x[N], y[N];
int s[N];
int posl[N], posr[N], sa[N], rk[N], id[N], cnt[N], rid[N], dep[N], top;
int al[N], ar[N], rans[N];
int sum[N], tot;
vector<pair<int, int> > e[N];
vector<int> qr[N];
inline void add(int p, int v) {
  while (p <= tot) sum[p] += v, p += p & (-p);
}
inline int ask(int p) {
  int ret = 0;
  while (p) ret += sum[p], p -= p & (-p);
  return ret;
}
void SA(int n) {
  for (int i = 1; i <= n; ++i) ++cnt[s[i]];
  int m = 27;
  for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (int i = 1; i <= n; ++i) sa[cnt[rk[i] = s[i]]--] = i;
  for (int len = 1; len == 1 || m != n; len <<= 1) {
    top = 0;
    for (int i = n - len + 1; i <= n; ++i) id[++top] = i;
    for (int i = 1; i <= n; ++i)
      if (sa[i] > len) id[++top] = sa[i] - len;
    std::fill(cnt, cnt + m + 1, 0);
    for (int i = 1; i <= n; ++i) ++cnt[rk[i]], rid[i] = rk[id[i]];
    for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (int i = top; i; --i) sa[cnt[rid[i]]--] = id[i];
    std::copy(rk + 1, rk + n + 1, rid + 1);
    auto cmp = [&](int x, int y) {
      return rid[x] == rid[y] && (x + len > n ? 0 : rid[x + len]) ==
                                     (y + len > n ? 0 : rid[y + len]);
    };
    m = 0;
    for (int i = 1; i <= n; ++i) {
      if (i == 1 || !cmp(sa[i - 1], sa[i])) ++m;
      rk[sa[i]] = m;
    }
  }
}
int ul[N][20], ur[N][20], dl[N][20], dr[N][20], pa[N][20];
inline bool cmple(int xl, int xr, int y, int p, int len) {
  return (xl <= rk[p] && rk[p] <= xr) ? y <= (p + len > tot ? 0 : rk[p + len])
                                      : xl < rk[p];
}
inline void merge(int xl, int xr, int yl, int yr, int len, int &x, int &y) {
  int l = 0, r = tot;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (cmple(xl, xr, yl, sa[mid], len))
      r = mid - 1;
    else
      l = mid;
  }
  x = l + 1;
  r = tot;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (cmple(xl, xr, yr + 1, sa[mid], len))
      r = mid - 1;
    else
      l = mid;
  }
  y = l;
}
void dfs(int u, int fa, int w) {
  pa[u][0] = fa;
  dep[u] = dep[fa] + 1;
  ul[u][0] = dl[u][0] = al[w], ur[u][0] = dr[u][0] = ar[w];
  for (int i = 1; (1 << i) <= n; ++i) {
    pa[u][i] = pa[pa[u][i - 1]][i - 1];
    if (!pa[u][i]) break;
    merge(ul[u][i - 1], ur[u][i - 1], ul[pa[u][i - 1]][i - 1],
          ur[pa[u][i - 1]][i - 1], (1 << (i - 1)), ul[u][i], ur[u][i]);
    int len = 1 << (i - 1);
    merge(dl[pa[u][i - 1]][i - 1], dr[pa[u][i - 1]][i - 1], dl[u][i - 1],
          dr[u][i - 1], len, dl[u][i], dr[u][i]);
  }
  for (auto [v, c] : e[u])
    if (v != fa) {
      dfs(v, u, c);
    }
}
inline int lca(int x, int y) {
  if (dep[x] < dep[y]) std::swap(x, y);
  for (int i = 19; ~i; --i)
    if (dep[pa[x][i]] >= dep[y]) x = pa[x][i];
  if (x == y) return x;
  for (int i = 19; ~i; --i)
    if (pa[x][i] != pa[y][i]) x = pa[x][i], y = pa[y][i];
  return pa[x][0];
}
void find(int x, int y, int &cl, int &cr) {
  int l = lca(x, y);
  int xl = 0, xr = tot, yl = 0, yr = tot;
  int cur = 0;
  for (int i = 19; ~i; --i)
    if (dep[pa[x][i]] >= dep[l]) {
      merge(xl, xr, ul[x][i], ur[x][i], cur, xl, xr);
      cur |= (1 << i);
      x = pa[x][i];
    }
  for (int i = 19; ~i; --i)
    if (dep[pa[y][i]] >= dep[l]) {
      merge(dl[y][i], dr[y][i], yl, yr, 1 << i, yl, yr);
      y = pa[y][i];
    }
  merge(xl, xr, yl, yr, cur, cl, cr);
}
char t[N];
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1, x, y; i < n; ++i) {
    scanf("%d%d%s", &x, &y, t);
    e[x].push_back({y, t[0] - 'a' + 1});
    e[y].push_back({x, t[0] - 'a' + 1});
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%s", t + 1);
    int len = strlen(t + 1);
    for (int i = 1; i <= len; ++i) s[tot + i] = t[i] - 'a' + 1;
    posl[i] = tot + 1, posr[i] = tot + len;
    s[tot + len + 1] = 27;
    tot += len + 1;
  }
  SA(tot);
  for (int i = 0; i <= 19; ++i) ur[0][i] = dr[0][i] = tot;
  ar[0] = tot;
  std::fill(al + 1, al + 27 + 1, tot + 1);
  for (int i = 1; i <= tot; ++i)
    if (s[i] <= 26) {
      al[s[i]] = std::min(al[s[i]], rk[i]);
      ar[s[i]] = std::max(ar[s[i]], rk[i]);
    }
  dfs(1, 0, 0);
  for (int i = 1, l, r; i <= q; ++i) {
    scanf("%d%d%d%d", x + i, y + i, &l, &r);
    qr[l - 1].push_back(-i);
    qr[r].push_back(i);
  }
  for (int i = 1; i <= m; ++i) {
    int l, r;
    for (int j = posl[i]; j <= posr[i]; ++j) add(rk[j], 1);
    for (int _x : qr[i]) {
      int x = std::abs(_x);
      find(::x[x], y[x], l, r);
      int v = ask(r) - ask(l - 1);
      if (_x < 0)
        rans[x] -= v;
      else
        rans[x] += v;
    }
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", rans[i]);
  return 0;
}

```