#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, L = 17, D = 1e9 + 7, W = 27;
char s[N];
pair<int, int> seg[N];
int nex_r[N], dy_r[N];
vector<pair<int, char>> lk[N];
int dep[N], f[N][L];
long long rt_to[N][L], to_rt[N][L], pow_W[N], h[N][L];
void dfs(int x, int fr) {
  f[x][0] = fr;
  dep[x] = dep[fr] + 1;
  for (int i = 1; i < L; ++i) {
    int y = f[x][i - 1];
    f[x][i] = f[y][i - 1];
    rt_to[x][i] = (rt_to[y][i - 1] * pow_W[1 << (i - 1)] + rt_to[x][i - 1]) % D;
    to_rt[x][i] = (to_rt[x][i - 1] * pow_W[1 << (i - 1)] + to_rt[y][i - 1]) % D;
  }
  for (auto pr : lk[x]) {
    int y;
    char c;
    tie(y, c) = pr;
    if (y != fr) {
      rt_to[y][0] = to_rt[y][0] = c;
      dfs(y, x);
    }
  }
}
namespace BIT {
int c[N];
void add(int x) {
  for (int i = x; i < N; i += i & -i) ++c[i];
}
int query(int x) {
  int ans = 0;
  for (int i = x; i; i -= i & -i) ans += c[i];
  return ans;
}
int query(int l, int r) { return query(r) - query(l - 1); }
}  // namespace BIT
namespace SA {
int qa[2][N];
int sa[N], h[N], *rk = qa[0], *tmp = qa[1];
int cnt[N];
void get_sa(int n) {
  for (int i = 1; i <= n; ++i) ++cnt[s[i]];
  for (int i = 1; i <= 128; ++i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; --i) sa[cnt[s[i]]--] = i;
  int m = 1;
  rk[sa[1]] = 1;
  for (int i = 2; i <= n; ++i) {
    if (s[sa[i]] != s[sa[i - 1]]) ++m;
    rk[sa[i]] = m;
  }
  for (int l = 1; m < n; l *= 2) {
    int top = 0;
    for (int i = n - l + 1; i <= n; ++i) tmp[++top] = i;
    for (int i = 1; i <= n; ++i)
      if (sa[i] > l) tmp[++top] = sa[i] - l;
    memset(cnt + 1, 0, m * sizeof(int));
    for (int i = 1; i <= n; ++i) ++cnt[rk[i]];
    for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; --i) sa[cnt[rk[tmp[i]]]--] = tmp[i];
    swap(rk, tmp);
    m = 1;
    rk[sa[1]] = 1;
    for (int i = 2; i <= n; ++i) {
      int now = sa[i], last = sa[i - 1];
      if (tmp[now] != tmp[last] || tmp[now + l] != tmp[last + l]) ++m;
      rk[now] = m;
    }
  }
  int l = 0;
  for (int i = 1; i <= n; ++i) {
    if (l) --l;
    int now = rk[i];
    while (s[i + l] == s[sa[now + 1] + l]) ++l;
    h[now] = l;
  }
}
};  // namespace SA
int qu[N], qv[N];
vector<pair<int, int>> lkq[N];
int ans[N], tot;
int get_lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int j = L - 1; j >= 0; --j)
    if (dep[x] - dep[y] & (1 << j)) x = f[x][j];
  if (x == y) return x;
  for (int j = L - 1; j >= 0; --j)
    if (f[x][j] != f[y][j]) {
      x = f[x][j];
      y = f[y][j];
    }
  return f[x][0];
}
int query(int u, int v) {
  int lca = get_lca(u, v);
  int du = dep[u] - dep[lca], dv = dep[v] - dep[lca];
  static int _v[L];
  for (int j = 0; j < L; ++j)
    if (dv & (1 << j)) {
      _v[j] = v;
      v = f[v][j];
    }
  auto cmp_le = [&](const pair<int, int>& seg) -> bool {
    int l, r;
    tie(l, r) = seg;
    int nu = u;
    for (int j = 0; j < L; ++j)
      if (du & (1 << j)) {
        if (h[l][j] != to_rt[nu][j]) {
          while (j) {
            --j;
            if (h[l][j] == to_rt[nu][j]) {
              l += 1 << j;
              nu = f[nu][j];
            }
          }
          return h[l][0] < to_rt[nu][0];
        }
        l += 1 << j;
        nu = f[nu][j];
      }
    for (int j = L - 1; j >= 0; --j)
      if (dv & (1 << j)) {
        int nv = _v[j];
        if (h[l][j] != rt_to[nv][j]) {
          while (j) {
            --j;
            if (h[l][j] == rt_to[f[nv][j]][j]) {
              l += 1 << j;
            } else
              nv = f[nv][j];
          }
          return h[l][0] < rt_to[nv][0];
        }
        l += 1 << j;
      }
    return 0;
  };
  auto cmp_eq = [&](const pair<int, int>& seg) -> bool {
    int l, r;
    tie(l, r) = seg;
    int nu = u;
    for (int j = 0; j < L; ++j)
      if (du & (1 << j)) {
        if (h[l][j] != to_rt[nu][j]) return 0;
        l += 1 << j;
        nu = f[nu][j];
      }
    for (int j = L - 1; j >= 0; --j)
      if (dv & (1 << j)) {
        int nv = _v[j];
        if (h[l][j] != rt_to[nv][j]) return 0;
        l += 1 << j;
      }
    return 1;
  };
  int l = 0, r = tot + 1;
  while (l + 1 != r) {
    int mid = (l + r) / 2;
    if (cmp_le(seg[mid]))
      l = mid;
    else
      r = mid;
  }
  int ans = -BIT::query(l);
  r = tot + 1;
  while (l + 1 != r) {
    int mid = (l + r) / 2;
    if (cmp_eq(seg[mid]))
      l = mid;
    else
      r = mid;
  }
  return ans + BIT::query(l);
}
int main() {
  pow_W[0] = 1;
  for (int i = 1; i < N; ++i) pow_W[i] = pow_W[i - 1] * W % D;
  int n, m, q;
  cin >> n >> m >> q;
  for (int i = 1; i < n; ++i) {
    int u, v;
    static char c[10];
    scanf("%d%d%s", &u, &v, c);
    lk[u].push_back({v, *c});
    lk[v].push_back({u, *c});
  }
  dfs(1, 0);
  for (int i = 1; i <= m; ++i) {
    int t = dy_r[i - 1] + 2;
    scanf("%s", s + t);
    dy_r[i] = t + strlen(s + t) - 1;
    for (int j = t; j <= dy_r[i]; ++j) nex_r[j] = dy_r[i];
    for (int j = dy_r[i]; j >= t; --j) {
      h[j][0] = s[j];
      for (int k = 1; k < L; ++k) {
        if (j + (1 << k) - 1 <= dy_r[i])
          h[j][k] =
              (h[j][k - 1] * pow_W[1 << (k - 1)] + h[j + (1 << k - 1)][k - 1]) %
              D;
        else
          h[j][k] = -1;
      }
    }
  }
  SA::get_sa(dy_r[m]);
  tot = 0;
  static int np[N];
  for (int i = 1; i <= dy_r[m]; ++i) {
    int j = SA::sa[i];
    if (nex_r[j]) seg[np[j] = ++tot] = {j, nex_r[j]};
  }
  for (int i = 1; i <= q; ++i) {
    int u, v, l, r;
    scanf("%d%d%d%d", &u, &v, &l, &r);
    qu[i] = u;
    qv[i] = v;
    lkq[l - 1].push_back({i, -1});
    lkq[r].push_back({i, 1});
  }
  for (int i = 1; i <= m; ++i) {
    for (int j = dy_r[i - 1] + 2; j <= dy_r[i]; ++j) {
      BIT::add(np[j]);
    }
    for (auto pr : lkq[i]) {
      int j, w;
      tie(j, w) = pr;
      ans[j] += query(qu[j], qv[j]) * w;
    }
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
}

### 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 = 2e5 + 5, L = 17, D = 1e9 + 7, W = 27;
char s[N];
pair<int, int> seg[N];
int nex_r[N], dy_r[N];
vector<pair<int, char>> lk[N];
int dep[N], f[N][L];
long long rt_to[N][L], to_rt[N][L], pow_W[N], h[N][L];
void dfs(int x, int fr) {
  f[x][0] = fr;
  dep[x] = dep[fr] + 1;
  for (int i = 1; i < L; ++i) {
    int y = f[x][i - 1];
    f[x][i] = f[y][i - 1];
    rt_to[x][i] = (rt_to[y][i - 1] * pow_W[1 << (i - 1)] + rt_to[x][i - 1]) % D;
    to_rt[x][i] = (to_rt[x][i - 1] * pow_W[1 << (i - 1)] + to_rt[y][i - 1]) % D;
  }
  for (auto pr : lk[x]) {
    int y;
    char c;
    tie(y, c) = pr;
    if (y != fr) {
      rt_to[y][0] = to_rt[y][0] = c;
      dfs(y, x);
    }
  }
}
namespace BIT {
int c[N];
void add(int x) {
  for (int i = x; i < N; i += i & -i) ++c[i];
}
int query(int x) {
  int ans = 0;
  for (int i = x; i; i -= i & -i) ans += c[i];
  return ans;
}
int query(int l, int r) { return query(r) - query(l - 1); }
}  // namespace BIT
namespace SA {
int qa[2][N];
int sa[N], h[N], *rk = qa[0], *tmp = qa[1];
int cnt[N];
void get_sa(int n) {
  for (int i = 1; i <= n; ++i) ++cnt[s[i]];
  for (int i = 1; i <= 128; ++i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; --i) sa[cnt[s[i]]--] = i;
  int m = 1;
  rk[sa[1]] = 1;
  for (int i = 2; i <= n; ++i) {
    if (s[sa[i]] != s[sa[i - 1]]) ++m;
    rk[sa[i]] = m;
  }
  for (int l = 1; m < n; l *= 2) {
    int top = 0;
    for (int i = n - l + 1; i <= n; ++i) tmp[++top] = i;
    for (int i = 1; i <= n; ++i)
      if (sa[i] > l) tmp[++top] = sa[i] - l;
    memset(cnt + 1, 0, m * sizeof(int));
    for (int i = 1; i <= n; ++i) ++cnt[rk[i]];
    for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; --i) sa[cnt[rk[tmp[i]]]--] = tmp[i];
    swap(rk, tmp);
    m = 1;
    rk[sa[1]] = 1;
    for (int i = 2; i <= n; ++i) {
      int now = sa[i], last = sa[i - 1];
      if (tmp[now] != tmp[last] || tmp[now + l] != tmp[last + l]) ++m;
      rk[now] = m;
    }
  }
  int l = 0;
  for (int i = 1; i <= n; ++i) {
    if (l) --l;
    int now = rk[i];
    while (s[i + l] == s[sa[now + 1] + l]) ++l;
    h[now] = l;
  }
}
};  // namespace SA
int qu[N], qv[N];
vector<pair<int, int>> lkq[N];
int ans[N], tot;
int get_lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int j = L - 1; j >= 0; --j)
    if (dep[x] - dep[y] & (1 << j)) x = f[x][j];
  if (x == y) return x;
  for (int j = L - 1; j >= 0; --j)
    if (f[x][j] != f[y][j]) {
      x = f[x][j];
      y = f[y][j];
    }
  return f[x][0];
}
int query(int u, int v) {
  int lca = get_lca(u, v);
  int du = dep[u] - dep[lca], dv = dep[v] - dep[lca];
  static int _v[L];
  for (int j = 0; j < L; ++j)
    if (dv & (1 << j)) {
      _v[j] = v;
      v = f[v][j];
    }
  auto cmp_le = [&](const pair<int, int>& seg) -> bool {
    int l, r;
    tie(l, r) = seg;
    int nu = u;
    for (int j = 0; j < L; ++j)
      if (du & (1 << j)) {
        if (h[l][j] != to_rt[nu][j]) {
          while (j) {
            --j;
            if (h[l][j] == to_rt[nu][j]) {
              l += 1 << j;
              nu = f[nu][j];
            }
          }
          return h[l][0] < to_rt[nu][0];
        }
        l += 1 << j;
        nu = f[nu][j];
      }
    for (int j = L - 1; j >= 0; --j)
      if (dv & (1 << j)) {
        int nv = _v[j];
        if (h[l][j] != rt_to[nv][j]) {
          while (j) {
            --j;
            if (h[l][j] == rt_to[f[nv][j]][j]) {
              l += 1 << j;
            } else
              nv = f[nv][j];
          }
          return h[l][0] < rt_to[nv][0];
        }
        l += 1 << j;
      }
    return 0;
  };
  auto cmp_eq = [&](const pair<int, int>& seg) -> bool {
    int l, r;
    tie(l, r) = seg;
    int nu = u;
    for (int j = 0; j < L; ++j)
      if (du & (1 << j)) {
        if (h[l][j] != to_rt[nu][j]) return 0;
        l += 1 << j;
        nu = f[nu][j];
      }
    for (int j = L - 1; j >= 0; --j)
      if (dv & (1 << j)) {
        int nv = _v[j];
        if (h[l][j] != rt_to[nv][j]) return 0;
        l += 1 << j;
      }
    return 1;
  };
  int l = 0, r = tot + 1;
  while (l + 1 != r) {
    int mid = (l + r) / 2;
    if (cmp_le(seg[mid]))
      l = mid;
    else
      r = mid;
  }
  int ans = -BIT::query(l);
  r = tot + 1;
  while (l + 1 != r) {
    int mid = (l + r) / 2;
    if (cmp_eq(seg[mid]))
      l = mid;
    else
      r = mid;
  }
  return ans + BIT::query(l);
}
int main() {
  pow_W[0] = 1;
  for (int i = 1; i < N; ++i) pow_W[i] = pow_W[i - 1] * W % D;
  int n, m, q;
  cin >> n >> m >> q;
  for (int i = 1; i < n; ++i) {
    int u, v;
    static char c[10];
    scanf("%d%d%s", &u, &v, c);
    lk[u].push_back({v, *c});
    lk[v].push_back({u, *c});
  }
  dfs(1, 0);
  for (int i = 1; i <= m; ++i) {
    int t = dy_r[i - 1] + 2;
    scanf("%s", s + t);
    dy_r[i] = t + strlen(s + t) - 1;
    for (int j = t; j <= dy_r[i]; ++j) nex_r[j] = dy_r[i];
    for (int j = dy_r[i]; j >= t; --j) {
      h[j][0] = s[j];
      for (int k = 1; k < L; ++k) {
        if (j + (1 << k) - 1 <= dy_r[i])
          h[j][k] =
              (h[j][k - 1] * pow_W[1 << (k - 1)] + h[j + (1 << k - 1)][k - 1]) %
              D;
        else
          h[j][k] = -1;
      }
    }
  }
  SA::get_sa(dy_r[m]);
  tot = 0;
  static int np[N];
  for (int i = 1; i <= dy_r[m]; ++i) {
    int j = SA::sa[i];
    if (nex_r[j]) seg[np[j] = ++tot] = {j, nex_r[j]};
  }
  for (int i = 1; i <= q; ++i) {
    int u, v, l, r;
    scanf("%d%d%d%d", &u, &v, &l, &r);
    qu[i] = u;
    qv[i] = v;
    lkq[l - 1].push_back({i, -1});
    lkq[r].push_back({i, 1});
  }
  for (int i = 1; i <= m; ++i) {
    for (int j = dy_r[i - 1] + 2; j <= dy_r[i]; ++j) {
      BIT::add(np[j]);
    }
    for (auto pr : lkq[i]) {
      int j, w;
      tie(j, w) = pr;
      ans[j] += query(qu[j], qv[j]) * w;
    }
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
}

```