#include <bits/stdc++.h>
using namespace std;
const int N = 100050;
const int M = 4 * N;
char s[M];
int fir[N], len[N], tot;
int id[M], sa[M], nsa[M], cnt[M], td[M], tmp[M];
void buildSuffixArray() {
  int mx = 0;
  for (int i = 0; i < tot; i++) id[i] = s[i], sa[i] = i, mx = max(mx, id[i]);
  sort(sa, sa + tot, [&](int i, int j) { return id[i] < id[j]; });
  for (int j = 1;; j <<= 1) {
    for (int i = 0; i <= mx; ++i) cnt[i] = 0;
    for (int i = 0; i < tot; ++i) cnt[id[i]]++;
    for (int i = 0, sum = 0; i <= mx; i++) sum += cnt[i], cnt[i] = sum - cnt[i];
    for (int i = 0; i < tot; ++i) {
      int k = sa[i];
      if (k >= j) nsa[cnt[id[k - j]]++] = k - j;
      td[i] = i + j < tot ? id[i + j] : 0;
    }
    for (int i = tot - j; i < tot; ++i) nsa[cnt[id[i]]++] = i;
    for (int i = 0; i < tot; ++i) sa[i] = nsa[i];
    int c = 0;
    for (int i = 0; i < tot; ++i) {
      tmp[sa[i]] = c;
      c += i + 1 == tot || id[sa[i]] != id[sa[i + 1]] ||
           td[sa[i]] != td[sa[i + 1]];
      id[sa[i]] = tmp[sa[i]];
    }
    mx = c - 1;
    if (c == tot) break;
  }
}
int lcp[M];
void buildLCPArray() {
  for (int i = 0, k = 0; i < tot; i++) {
    if (id[i] + 1 != tot) {
      int j = sa[id[i] + 1];
      while (s[i + k] == s[j + k]) k++;
      lcp[id[i]] = k;
      if (k) k--;
    }
  }
}
const int L = 19;
int rmq[M][L], lgs[M];
void buildSparseTable() {
  for (int i = 2; i <= tot; i++) lgs[i] = lgs[i >> 1] + 1;
  for (int i = 0; i < tot; i++) rmq[i][0] = lcp[i];
  for (int j = 1; j < L; j++)
    for (int i = 0; i < tot - (1 << j) + 1; i++)
      rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << j - 1)][j - 1]);
}
int LCP(int i, int j) {
  i = id[i];
  j = id[j];
  if (i > j) swap(i, j);
  if (i == j) return tot - sa[i];
  j--;
  int k = lgs[j - i + 1];
  return min(rmq[i][k], rmq[j - (1 << k) + 1][k]);
}
int LCP(int st, const vector<pair<int, int>>& path, char& nxt) {
  int ans = 0;
  for (int i = 0; i < path.size(); i++) {
    int now = LCP(st + ans, path[i].first);
    if (now >= path[i].second) {
      ans += path[i].second;
    } else {
      ans += now;
      nxt = s[path[i].first + now];
      return ans;
    }
  }
  nxt = 0;
  return ans;
}
int cmp(int st, const vector<pair<int, int>>& path) {
  char nxt = 0;
  int pref = LCP(st, path, nxt);
  if (nxt == 0) return 0;
  return s[st + pref] < nxt ? -1 : 1;
}
struct BIT {
  int sum[M];
  BIT() {}
  void Add(int i, int f) {
    for (i++; i < M; i += i & -i) sum[i] += f;
  }
  int Get(int i) {
    int ans = 0;
    for (i++; i; i -= i & -i) ans += sum[i];
    return ans;
  }
} BT;
vector<pair<int, char>> E[N];
int sz[N], par[N], lid[N], head[N], tid, dep[N];
char ch[N];
void DFS(int u, int p) {
  par[u] = p;
  sz[u] = 1;
  dep[u] = dep[p] + 1;
  for (auto v : E[u])
    if (v.first != p) {
      DFS(v.first, u);
      sz[u] += sz[v.first];
      ch[v.first] = v.second;
    }
}
void HLD(int u, int p) {
  if (!head[u]) head[u] = u;
  lid[u] = ++tid;
  int HC = 0;
  for (auto v : E[u])
    if (v.first != p && sz[v.first] > sz[HC]) HC = v.first;
  if (HC) {
    head[HC] = head[u];
    HLD(HC, u);
  }
  for (auto v : E[u])
    if (v.first != p && v.first != HC) HLD(v.first, u);
}
int soh, n, m, q;
vector<pair<int, int>> getPath(int u, int v) {
  vector<pair<int, int>> fw, bw;
  while (head[u] != head[v]) {
    if (dep[head[u]] > dep[head[v]]) {
      fw.push_back({soh + (n - 1) + (n - lid[u]), dep[u] - dep[head[u]] + 1});
      u = par[head[u]];
    } else {
      bw.push_back({soh + lid[head[v]] - 2, dep[v] - dep[head[v]] + 1});
      v = par[head[v]];
    }
  }
  if (dep[u] > dep[v]) {
    fw.push_back({soh + (n - 1) + (n - lid[u]), dep[u] - dep[v]});
  } else if (dep[v] > dep[u]) {
    bw.push_back({soh + lid[u] - 1, dep[v] - dep[u]});
  }
  for (int i = bw.size(); i > 0; i--) fw.push_back(bw[i - 1]);
  return fw;
}
int qu[N], qv[N], ql[N], qr[N], ans[N], sal[N], sar[N];
vector<pair<int, int>> Qs[N];
int main() {
  scanf("%i %i %i", &n, &m, &q);
  for (int i = 1; i < n; i++) {
    int u, v;
    char c;
    scanf("%i %i %c", &u, &v, &c);
    E[u].push_back({v, c});
    E[v].push_back({u, c});
  }
  for (int i = 1; i <= m; i++) {
    scanf("%s", s + fir[i]);
    len[i] = strlen(s + fir[i]);
    s[fir[i] + len[i]] = 'a' - 1;
    fir[i + 1] = fir[i] + len[i] + 1;
  }
  DFS(1, 0);
  HLD(1, 0);
  soh = fir[m + 1];
  for (int i = 2; i <= n; i++) {
    s[soh + lid[i] - 2] = ch[i];
    s[soh + (n - 1) + (n - lid[i])] = ch[i];
  }
  s[soh + (n - 1) * 2] = 'a' - 2;
  tot = soh + (n - 1) * 2 + 1;
  buildSuffixArray();
  buildLCPArray();
  buildSparseTable();
  for (int i = 1; i <= q; i++) {
    scanf("%i %i %i %i", &qu[i], &qv[i], &ql[i], &qr[i]);
    Qs[ql[i] - 1].push_back({i, -1});
    Qs[qr[i]].push_back({i, 1});
    vector<pair<int, int>> path = getPath(qu[i], qv[i]);
    int top = tot - 1, bot = 0;
    while (top >= bot) {
      int mid = top + bot >> 1;
      if (cmp(sa[mid], path) < 0) {
        sal[i] = mid;
        bot = mid + 1;
      } else
        top = mid - 1;
    }
    top = tot - 1, bot = 0;
    while (top >= bot) {
      int mid = top + bot >> 1;
      if (cmp(sa[mid], path) <= 0) {
        sar[i] = mid;
        bot = mid + 1;
      } else
        top = mid - 1;
    }
  }
  for (int i = 1; i <= m; i++) {
    for (int o = fir[i]; o < fir[i] + len[i]; o++) {
      BT.Add(id[o], 1);
    }
    for (auto qq : Qs[i]) {
      int qi = qq.first;
      int mul = qq.second;
      ans[qi] += mul * (BT.Get(sar[qi]) - BT.Get(sal[qi]));
    }
  }
  for (int i = 1; i <= q; i++) printf("%i\n", ans[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 namespace std;
const int N = 100050;
const int M = 4 * N;
char s[M];
int fir[N], len[N], tot;
int id[M], sa[M], nsa[M], cnt[M], td[M], tmp[M];
void buildSuffixArray() {
  int mx = 0;
  for (int i = 0; i < tot; i++) id[i] = s[i], sa[i] = i, mx = max(mx, id[i]);
  sort(sa, sa + tot, [&](int i, int j) { return id[i] < id[j]; });
  for (int j = 1;; j <<= 1) {
    for (int i = 0; i <= mx; ++i) cnt[i] = 0;
    for (int i = 0; i < tot; ++i) cnt[id[i]]++;
    for (int i = 0, sum = 0; i <= mx; i++) sum += cnt[i], cnt[i] = sum - cnt[i];
    for (int i = 0; i < tot; ++i) {
      int k = sa[i];
      if (k >= j) nsa[cnt[id[k - j]]++] = k - j;
      td[i] = i + j < tot ? id[i + j] : 0;
    }
    for (int i = tot - j; i < tot; ++i) nsa[cnt[id[i]]++] = i;
    for (int i = 0; i < tot; ++i) sa[i] = nsa[i];
    int c = 0;
    for (int i = 0; i < tot; ++i) {
      tmp[sa[i]] = c;
      c += i + 1 == tot || id[sa[i]] != id[sa[i + 1]] ||
           td[sa[i]] != td[sa[i + 1]];
      id[sa[i]] = tmp[sa[i]];
    }
    mx = c - 1;
    if (c == tot) break;
  }
}
int lcp[M];
void buildLCPArray() {
  for (int i = 0, k = 0; i < tot; i++) {
    if (id[i] + 1 != tot) {
      int j = sa[id[i] + 1];
      while (s[i + k] == s[j + k]) k++;
      lcp[id[i]] = k;
      if (k) k--;
    }
  }
}
const int L = 19;
int rmq[M][L], lgs[M];
void buildSparseTable() {
  for (int i = 2; i <= tot; i++) lgs[i] = lgs[i >> 1] + 1;
  for (int i = 0; i < tot; i++) rmq[i][0] = lcp[i];
  for (int j = 1; j < L; j++)
    for (int i = 0; i < tot - (1 << j) + 1; i++)
      rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << j - 1)][j - 1]);
}
int LCP(int i, int j) {
  i = id[i];
  j = id[j];
  if (i > j) swap(i, j);
  if (i == j) return tot - sa[i];
  j--;
  int k = lgs[j - i + 1];
  return min(rmq[i][k], rmq[j - (1 << k) + 1][k]);
}
int LCP(int st, const vector<pair<int, int>>& path, char& nxt) {
  int ans = 0;
  for (int i = 0; i < path.size(); i++) {
    int now = LCP(st + ans, path[i].first);
    if (now >= path[i].second) {
      ans += path[i].second;
    } else {
      ans += now;
      nxt = s[path[i].first + now];
      return ans;
    }
  }
  nxt = 0;
  return ans;
}
int cmp(int st, const vector<pair<int, int>>& path) {
  char nxt = 0;
  int pref = LCP(st, path, nxt);
  if (nxt == 0) return 0;
  return s[st + pref] < nxt ? -1 : 1;
}
struct BIT {
  int sum[M];
  BIT() {}
  void Add(int i, int f) {
    for (i++; i < M; i += i & -i) sum[i] += f;
  }
  int Get(int i) {
    int ans = 0;
    for (i++; i; i -= i & -i) ans += sum[i];
    return ans;
  }
} BT;
vector<pair<int, char>> E[N];
int sz[N], par[N], lid[N], head[N], tid, dep[N];
char ch[N];
void DFS(int u, int p) {
  par[u] = p;
  sz[u] = 1;
  dep[u] = dep[p] + 1;
  for (auto v : E[u])
    if (v.first != p) {
      DFS(v.first, u);
      sz[u] += sz[v.first];
      ch[v.first] = v.second;
    }
}
void HLD(int u, int p) {
  if (!head[u]) head[u] = u;
  lid[u] = ++tid;
  int HC = 0;
  for (auto v : E[u])
    if (v.first != p && sz[v.first] > sz[HC]) HC = v.first;
  if (HC) {
    head[HC] = head[u];
    HLD(HC, u);
  }
  for (auto v : E[u])
    if (v.first != p && v.first != HC) HLD(v.first, u);
}
int soh, n, m, q;
vector<pair<int, int>> getPath(int u, int v) {
  vector<pair<int, int>> fw, bw;
  while (head[u] != head[v]) {
    if (dep[head[u]] > dep[head[v]]) {
      fw.push_back({soh + (n - 1) + (n - lid[u]), dep[u] - dep[head[u]] + 1});
      u = par[head[u]];
    } else {
      bw.push_back({soh + lid[head[v]] - 2, dep[v] - dep[head[v]] + 1});
      v = par[head[v]];
    }
  }
  if (dep[u] > dep[v]) {
    fw.push_back({soh + (n - 1) + (n - lid[u]), dep[u] - dep[v]});
  } else if (dep[v] > dep[u]) {
    bw.push_back({soh + lid[u] - 1, dep[v] - dep[u]});
  }
  for (int i = bw.size(); i > 0; i--) fw.push_back(bw[i - 1]);
  return fw;
}
int qu[N], qv[N], ql[N], qr[N], ans[N], sal[N], sar[N];
vector<pair<int, int>> Qs[N];
int main() {
  scanf("%i %i %i", &n, &m, &q);
  for (int i = 1; i < n; i++) {
    int u, v;
    char c;
    scanf("%i %i %c", &u, &v, &c);
    E[u].push_back({v, c});
    E[v].push_back({u, c});
  }
  for (int i = 1; i <= m; i++) {
    scanf("%s", s + fir[i]);
    len[i] = strlen(s + fir[i]);
    s[fir[i] + len[i]] = 'a' - 1;
    fir[i + 1] = fir[i] + len[i] + 1;
  }
  DFS(1, 0);
  HLD(1, 0);
  soh = fir[m + 1];
  for (int i = 2; i <= n; i++) {
    s[soh + lid[i] - 2] = ch[i];
    s[soh + (n - 1) + (n - lid[i])] = ch[i];
  }
  s[soh + (n - 1) * 2] = 'a' - 2;
  tot = soh + (n - 1) * 2 + 1;
  buildSuffixArray();
  buildLCPArray();
  buildSparseTable();
  for (int i = 1; i <= q; i++) {
    scanf("%i %i %i %i", &qu[i], &qv[i], &ql[i], &qr[i]);
    Qs[ql[i] - 1].push_back({i, -1});
    Qs[qr[i]].push_back({i, 1});
    vector<pair<int, int>> path = getPath(qu[i], qv[i]);
    int top = tot - 1, bot = 0;
    while (top >= bot) {
      int mid = top + bot >> 1;
      if (cmp(sa[mid], path) < 0) {
        sal[i] = mid;
        bot = mid + 1;
      } else
        top = mid - 1;
    }
    top = tot - 1, bot = 0;
    while (top >= bot) {
      int mid = top + bot >> 1;
      if (cmp(sa[mid], path) <= 0) {
        sar[i] = mid;
        bot = mid + 1;
      } else
        top = mid - 1;
    }
  }
  for (int i = 1; i <= m; i++) {
    for (int o = fir[i]; o < fir[i] + len[i]; o++) {
      BT.Add(id[o], 1);
    }
    for (auto qq : Qs[i]) {
      int qi = qq.first;
      int mul = qq.second;
      ans[qi] += mul * (BT.Get(sar[qi]) - BT.Get(sal[qi]));
    }
  }
  for (int i = 1; i <= q; i++) printf("%i\n", ans[i]);
  return 0;
}

```