Problem: As we all know, Eleven has special abilities. Thus, Hopper convinced her to close the gate to the Upside Down World with her mind. Upside down monsters like to move between the worlds, so they are going to attack Hopper and Eleven in order to make them stop. The monsters live in the vines. The vines form a tree with n vertices, numbered from 1 through n. There's a lowercase English letter written in each tunnel (edge).

<image>

Upside down is a magical world. There are m types of monsters in upside down, numbered from 1 through m. Each type of monster has a special word that gives them powers. The special word of type i is si. There are q monsters in upside down. Each one is at a junction (vertex) and is going to some other junction. If monster of type k goes from junction i to junction j, the power it gains is the number of times it sees its special world (sk) consecutively in the tunnels. More formally: 

If f(i, j) is the string we get when we concatenate the letters written in the tunnels on the shortest path from i to j, then the power the monster gains is the number of occurrences of sk in f(i, j).

Hopper and Eleven want to get prepared, so for each monster, they want to know the power the monster gains after moving. 

Input

The first line of input contains three integers, n, m and q (2 ≤ n ≤ 105, 1 ≤ m, q ≤ 105).

The next n - 1 lines contain the tunnels (edges). Each line contains two integers v and u (1 ≤ v, u ≤ n, v ≠ u) and a lowercase English letter c, meaning there's a tunnel connecting junctions v and u written c in it. It is guaranteed that the given graph is a tree.

The next m lines contain the special words. i-th line of them contains a single string si (1 ≤ |si| ≤ 105), consisting of lowercase English letters. It is guaranteed that |s1| + |s2| + ... + |sm| ≤ 105).

The next q lines contain the monsters. Each line contains three integers i, j and k (1 ≤ i, j ≤ n, i ≠ j, 1 ≤ k ≤ m), meaning a monster of type k is going from junction number i to junction number j.

Output

Print q lines. i-th line should contain a single integer, the power the i-th monster gains after moving.

Examples

Input

6 4 5
1 6 b
2 3 a
1 2 b
5 3 b
4 5 b
a
b
bb
aa
1 2 1
6 2 3
1 6 2
4 5 4
1 6 2


Output

0
1
1
0
1


Input

10 6 7
1 3 s
10 1 d
2 6 s
5 2 d
7 4 l
8 9 d
8 10 l
7 2 d
8 7 l
dl
dssld
d
d
l
sl
4 5 4
3 7 5
10 6 2
3 1 4
7 5 6
10 9 4
9 8 4


Output

2
2
0
0
0
1
1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
namespace _ {
const int inf = 1e9 + 7;
namespace _in {
template <class T>
inline T read() {
  char ch;
  bool flag = 0;
  T x = 0;
  while (ch = getchar(), !isdigit(ch))
    if (ch == '-') flag = 1;
  while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
  return flag ? -x : x;
}
struct {
  inline operator long long() { return read<long long>(); }
  inline operator int() { return read<int>(); }
  inline operator bool() { return read<bool>(); }
  template <class T>
  inline void operator()(T &x) {
    x = *this;
  }
  template <class T, class... A>
  inline void operator()(T &x, A &...a) {
    x = *this, this->operator()(a...);
  }
} IN;
}  // namespace _in
using namespace _in;
namespace _std {
template <class T>
inline void swap(T &x, T &y) {
  x ^= y ^= x ^= y;
}
template <class T>
inline T max(T x, T y) {
  if (x < y) x = y;
  return x;
}
template <class T>
inline T min(T x, T y) {
  if (x > y) x = y;
  return x;
}
template <class T>
inline void chkmax(T &x, T y) {
  if (x < y) x = y;
}
template <class T>
inline void chkmin(T &x, T y) {
  if (x > y) x = y;
}
}  // namespace _std
using namespace _std;
}  // namespace _
using namespace _;
const int N = 1e5 + 5;
const int LogN = 19;
struct Edge_Node {
  int to, val;
};
struct Query {
  int id1, id2, typ, val;
};
char tmp_str[N];
int n, m, q, ans[N], fa_ch[N], len_str[N];
int *str[N];
std::vector<Edge_Node> son[N];
std::vector<Query> que_nod[N];
namespace Hash {
const std::pair<unsigned long long, unsigned long long> base =
    std::pair<unsigned long long, unsigned long long>(37, 137);
inline std::pair<unsigned long long, unsigned long long> operator+(
    const std::pair<unsigned long long, unsigned long long> &a,
    const std::pair<unsigned long long, unsigned long long> &b) {
  return std::pair<unsigned long long, unsigned long long>(a.first + b.first,
                                                           a.second + b.second);
}
inline std::pair<unsigned long long, unsigned long long> operator-(
    const std::pair<unsigned long long, unsigned long long> &a,
    const std::pair<unsigned long long, unsigned long long> &b) {
  return std::pair<unsigned long long, unsigned long long>(a.first - b.first,
                                                           a.second - b.second);
}
inline std::pair<unsigned long long, unsigned long long> operator*(
    const std::pair<unsigned long long, unsigned long long> &a,
    const std::pair<unsigned long long, unsigned long long> &b) {
  return std::pair<unsigned long long, unsigned long long>(a.first * b.first,
                                                           a.second * b.second);
}
inline bool operator==(
    const std::pair<unsigned long long, unsigned long long> &a,
    const std::pair<unsigned long long, unsigned long long> &b) {
  return (a.first == b.first) && (a.second == b.second);
}
}  // namespace Hash
using namespace Hash;
struct BIT {
  int lim, res, c[N];
  inline int lowbit(int x) { return x & (-x); }
  inline void update(int x, int y) {
    for (; x <= lim; x += lowbit(x)) c[x] += y;
  }
  inline int _sum(int x) {
    res = 0;
    for (; x; x -= lowbit(x)) res += c[x];
    return res;
  }
  inline int query(int l, int r) { return _sum(r) - _sum(l - 1); }
} bit[2];
struct AC_AutoMaton {
  std::queue<int> que;
  std::vector<int> son[N];
  int tot, tim, ch[N][26], fail[N], pos[N], dfn[N], siz[N];
  inline void build() {
    for (int i = 0; i < 26; ++i)
      if (ch[0][i]) fail[ch[0][i]] = 0, que.push(ch[0][i]);
    while (!que.empty()) {
      int u = que.front();
      que.pop();
      for (int c = 0; c < 26; ++c)
        if (ch[u][c])
          fail[ch[u][c]] = ch[fail[u]][c], que.push(ch[u][c]);
        else
          ch[u][c] = ch[fail[u]][c];
    }
  }
  inline void insert(int id) {
    int now = 0, len = len_str[id];
    for (int i = 1; i <= len; ++i) {
      if (!ch[now][str[id][i]]) ch[now][str[id][i]] = ++tot;
      now = ch[now][str[id][i]];
    }
    pos[id] = now;
  }
  void get_son() {
    for (int i = 1; i <= tot; ++i) son[fail[i]].push_back(i);
  }
  void pre_dfn(int u) {
    dfn[u] = ++tim, siz[u] = 1;
    for (int v : son[u]) pre_dfn(v), siz[u] += siz[v];
  }
} acm[2];
namespace LCA {
int dep[N], fa[N][LogN];
void get_fa(int u, int f) {
  fa[u][0] = f, dep[u] = dep[f] + 1;
  for (int i = 1; i < LogN; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  for (Edge_Node now : son[u])
    if (now.to != f) get_fa(now.to, u), fa_ch[now.to] = now.val;
}
inline int Lca(int x, int y) {
  if (x == y) return x;
  if (dep[x] < dep[y]) swap(x, y);
  for (int i = LogN - 1; ~i; --i)
    if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
  if (x == y) return x;
  for (int i = LogN - 1; ~i; --i)
    if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
  return fa[x][0];
}
inline int kth(int x, int d) {
  if (dep[x] < d) return -1;
  for (int i = LogN - 1; ~i; --i)
    if (dep[fa[x][i]] >= d) x = fa[x][i];
  return x;
}
}  // namespace LCA
using namespace LCA;
std::pair<unsigned long long, unsigned long long> sum[N], has_pow[N];
inline std::pair<unsigned long long, unsigned long long> tree_calc(int x,
                                                                   int y) {
  return sum[x] - sum[y] * has_pow[dep[x] - dep[y]];
}
int tot_bor[2];
struct Border {
  int s, t, d;
} border[N][2];
struct KMP {
  int n, *las, *nxt, *del;
  inline void build(int id) {
    n = len_str[id], nxt = new int[(n + 5)](), las = new int[(n + 5)](),
    del = new int[(n + 5)]();
    del[1] = las[1] = 1;
    for (int i = 2, t = 0; i <= n; ++i) {
      while (t && str[id][i] != str[id][t + 1]) t = nxt[t];
      if (str[id][i] == str[id][t + 1]) ++t;
      nxt[i] = t, del[i] = i - t, las[i] = (del[i] == del[t]) ? las[t] : i;
    }
  }
  inline void get_border(int pos, int len, int typ) {
    while (pos > len) pos = nxt[pos];
    while (pos > 0) {
      border[++tot_bor[typ]][typ] = (Border){las[pos], pos, del[pos]};
      pos = nxt[las[pos]];
    }
  }
} kmp[N][2];
int hep[N];
struct Suffix_Array {
  std::pair<unsigned long long, unsigned long long> *has;
  int n, m, *x, *y, *sa, *ch;
  inline std::pair<unsigned long long, unsigned long long> sa_calc(int l,
                                                                   int r) {
    return has[r] - has[l - 1] * has_pow[r - l + 1];
  }
  inline void sort() {
    for (int i = 0; i <= m; ++i) hep[i] = 0;
    for (int i = 1; i <= n; ++i) ++hep[x[i]];
    for (int i = 1; i <= m; ++i) hep[i] += hep[i - 1];
    for (int i = n; i >= 1; --i) sa[hep[x[y[i]]]--] = y[i];
  }
  inline void build(int id) {
    n = len_str[id], m = 126;
    x = new int[((n << 1) + 5)](), y = new int[((n << 1) + 5)](),
    sa = new int[(n + 5)](), ch = new int[(n + 5)]();
    has = new std::pair<unsigned long long, unsigned long long>[(n + 5)]();
    has[0] = std::pair<unsigned long long, unsigned long long>(1, 1);
    for (int i = 1; i <= n; ++i)
      has[i] =
          has[i - 1] * base + std::pair<unsigned long long, unsigned long long>(
                                  str[id][i], str[id][i]);
    for (int i = 1; i <= n; ++i)
      x[y[i] = i] = str[id][i] + 'a', ch[i] = str[id][i];
    sort();
    for (int w = 1, p = 0; m = p, p < n; w <<= 1) {
      for (int i = 1; i <= w; ++i) y[p = i] = n - w + i;
      for (int i = 1; i <= n; ++i)
        if (sa[i] > w) y[++p] = sa[i] - w;
      sort(), std::swap(x, y), x[sa[1]] = p = 1;
      for (int i = 2; i <= n; ++i)
        x[sa[i]] =
            (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + w] == y[sa[i - 1] + w])
                ? p
                : ++p;
    }
  }
  inline int lcp(int p, int u, int lca, int len = 0) {
    if (u == lca) return 0;
    p = sa[p], len = n - p + 1;
    if (len >= dep[u] - dep[lca] &&
        tree_calc(u, lca) == sa_calc(p, p + dep[u] - dep[lca] - 1))
      return dep[u] - dep[lca];
    else {
      int las;
      for (int i = LogN - 1; ~i; --i)
        if (dep[u] - dep[lca] > (1 << i)) {
          las = u, u = fa[u][i];
          if (len >= dep[u] - dep[lca] &&
              tree_calc(u, lca) == sa_calc(p, p + dep[u] - dep[lca] - 1))
            u = las;
        }
      u = fa[u][0];
      return dep[u] - dep[lca];
    }
  }
  inline bool check(int mid, int u, int lca) {
    int now = lcp(mid, u, lca);
    if (now == n - sa[mid] + 1) return true;
    if (now == dep[u] - dep[lca]) return false;
    return ch[sa[mid] + now] < fa_ch[kth(u, dep[lca] + now + 1)];
  }
  inline void get_maxlen(int u, int lca, int id, int typ) {
    int l = 1, r = n, mid, ans = 0;
    while (l <= r)
      check(mid = (l + r) >> 1, u, lca) ? ans = mid, l = mid + 1 : r = mid - 1;
    if (!ans) return;
    int len = lcp(ans, u, lca), pos = n - sa[ans] + 1;
    kmp[id][typ].get_border(pos, len, typ);
  }
} sa[N][2];
inline void addedge(int u = 0, int v = 0) {
  IN(u, v), scanf("%s", tmp_str);
  son[u].push_back((Edge_Node){v, tmp_str[0] - 'a'}),
      son[v].push_back((Edge_Node){u, tmp_str[0] - 'a'});
}
void get_ac_ans(int u, int t1, int t2) {
  bit[0].update(acm[0].dfn[t1], 1);
  bit[1].update(acm[1].dfn[t2], 1);
  for (Query now : que_nod[u]) {
    int id = now.id2, p = now.typ, v = now.val, k = acm[p].pos[now.id1];
    ans[id] +=
        v * bit[p].query(acm[p].dfn[k], acm[p].dfn[k] + acm[p].siz[k] - 1);
  }
  for (Edge_Node now : son[u]) {
    int v = now.to, c = now.val;
    if (v == fa[u][0]) continue;
    get_ac_ans(v, acm[0].ch[t1][c], acm[1].ch[t2][c]);
  }
  bit[0].update(acm[0].dfn[t1], -1);
  bit[1].update(acm[1].dfn[t2], -1);
}
void get_hash(int u) {
  for (Edge_Node now : son[u]) {
    int v = now.to, c = now.val;
    if (v == fa[u][0]) continue;
    sum[v] =
        sum[u] * base + std::pair<unsigned long long, unsigned long long>(c, c),
    get_hash(v);
  }
}
inline int exgcd(int a, int b, int &x, int &y) {
  if (!b) return x = 1, y = 0, a;
  int t = exgcd(b, a % b, y, x);
  return y -= a / b * x, t;
}
inline int get_ans(int a, int b, int la, int lb, int c) {
  int x, y, gcd = exgcd(a, b, x, y);
  if (c % gcd) return 0;
  x *= c / gcd, y *= c / gcd;
  int _a = a / gcd, _b = b / gcd, _x = (x % _b + _b) % _b;
  y += ((x - _x) / _b) * _a, x = _x;
  if (y < 0) return 0;
  if (y > lb) {
    int t = (y - lb - 1) / _a + 1;
    y -= t * _a, x += t * _b;
  }
  if (x < 0 || y < 0 || x > la || y > lb) return 0;
  return min((la - x) / _b + 1, y / _a + 1);
}
inline int kmp_solve(int u, int v, int lca, int id) {
  tot_bor[0] = tot_bor[1] = 0;
  sa[id][1].get_maxlen(u, lca, id, 0);
  sa[id][0].get_maxlen(v, lca, id, 1);
  int res = 0;
  for (int i = 1; i <= tot_bor[0]; ++i)
    for (int j = 1; j <= tot_bor[1]; ++j)
      if (border[i][0].s + border[j][1].s <= len_str[id] &&
          border[i][0].t + border[j][1].t >= len_str[id]) {
        int la = (border[i][0].t - border[i][0].s) / border[i][0].d;
        int lb = (border[j][1].t - border[j][1].s) / border[j][1].d;
        res += get_ans(border[i][0].d, border[j][1].d, la, lb,
                       len_str[id] - border[i][0].s - border[j][1].s);
      }
  return res;
}
int u, v, id;
int main() {
  IN(n, m, q);
  for (int i = 2; i <= n; ++i) addedge();
  get_fa(1, 0), get_hash(1);
  has_pow[0] = std::pair<unsigned long long, unsigned long long>(1, 1);
  for (int i = 1; i < N; ++i) has_pow[i] = has_pow[i - 1] * base;
  for (int i = 1; i <= m; ++i) {
    scanf("%s", tmp_str), len_str[i] = strlen(tmp_str);
    str[i] = new int[len_str[i] + 2]();
    for (int j = 1; j <= len_str[i]; ++j) str[i][j] = tmp_str[j - 1] - 'a';
    str[i][0] = str[i][len_str[i] + 1] = -1;
    acm[0].insert(i);
    sa[i][0].build(i);
    kmp[i][0].build(i);
    std::reverse(str[i] + 1, str[i] + 1 + len_str[i]);
    acm[1].insert(i);
    sa[i][1].build(i);
    kmp[i][1].build(i);
    std::reverse(str[i] + 1, str[i] + 1 + len_str[i]);
  }
  acm[0].build(), acm[0].get_son(), acm[0].pre_dfn(0);
  acm[1].build(), acm[1].get_son(), acm[1].pre_dfn(0);
  bit[0].lim = acm[0].tim, bit[1].lim = acm[1].tim;
  for (int t = 1; t <= q; ++t) {
    IN(u, v, id);
    int lca = Lca(u, v);
    ans[t] = kmp_solve(u, v, lca, id);
    int t1 = kth(u, min(dep[u], dep[lca] + len_str[id] - 1));
    int t2 = kth(v, min(dep[v], dep[lca] + len_str[id] - 1));
    if (t1 != u)
      que_nod[u].push_back((Query){id, t, 1, 1}),
          que_nod[t1].push_back((Query){id, t, 1, -1});
    if (t2 != v)
      que_nod[v].push_back((Query){id, t, 0, 1}),
          que_nod[t2].push_back((Query){id, t, 0, -1});
  }
  get_ac_ans(1, 0, 0);
  for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
  return 0;
}