Upside Down

우리 모두가 알다시피, Eleven에게는 특별한 능력이 있다. 그래서 Hopper는 그녀가 정신의 힘으로 Upside Down World로 통하는 문을 닫도록 설득했다. 뒤집힌 세계의 괴물들은 세계 사이를 이동하는 것을 좋아하므로, 그들은 이를 막으려는 Hopper and Eleven을 공격하려 한다. 괴물들은 덩굴 속에 산다. 덩굴은 정점이 n개인 트리를 이루며, 정점에는 1부터 n까지 번호가 매겨져 있다. 각 터널(간선)에는 영문 소문자 하나가 쓰여 있다.

뒤집힌 세계는 마법의 세계다. 뒤집힌 세계에는 괴물이 m가지 유형 있으며, 1부터 m까지 번호가 매겨져 있다. 각 유형의 괴물에게는 힘을 주는 특별한 단어가 있다. i 유형의 특별한 단어는 si이다. 뒤집힌 세계에는 괴물이 q마리 있다. 각 괴물은 교차점(정점) 하나에 있으며, 다른 교차점으로 이동하려 한다. k 유형의 괴물이 교차점 i에서 교차점 j으로 이동할 때, 얻는 힘은 터널에서 자신의 특별한 세계(sk)를 연속해서 보는 횟수이다. 더 형식적으로 설명하면 다음과 같다.

f(i, j)가 i에서 j까지의 최단 경로에 있는 터널들에 쓰인 문자들을 이어 붙여 얻는 문자열이라면, 괴물이 얻는 힘은 f(i, j)에서 sk가 등장하는 횟수이다.

Hopper and Eleven은 준비하고 싶어 하므로, 각 괴물이 이동한 뒤 얻는 힘을 알고 싶어 한다.

입력의 첫 번째 줄에는 세 정수 n, m, q가 주어진다 (2 ≤ n ≤ 105, 1 ≤ m, q ≤ 105).

다음 n - 1개의 줄에는 터널(간선)이 주어진다. 각 줄에는 두 정수 v, u와 영문 소문자 c가 주어진다 (1 ≤ v, u ≤ n, v ≠ u). 이는 교차점 v와 u을 연결하며 그 안에 c가 쓰인 터널이 있다는 뜻이다. 주어진 그래프가 트리임이 보장된다.

다음 m개의 줄에는 특별한 단어들이 주어진다. 그중 i-th 줄에는 영문 소문자로 이루어진 문자열 si 하나가 주어진다 (1 ≤ |si| ≤ 105). |s1| + |s2| + ... + |sm| ≤ 105임이 보장된다.

다음 q개의 줄에는 괴물들이 주어진다. 각 줄에는 세 정수 i, j, k가 주어진다 (1 ≤ i, j ≤ n, i ≠ j, 1 ≤ k ≤ m). 이는 k 유형의 괴물이 번호가 i인 교차점에서 번호가 j인 교차점으로 이동한다는 뜻이다.

q개의 줄을 출력한다. i-th 줄에는 i-th 괴물이 이동한 뒤 얻는 힘을 나타내는 정수 하나를 출력한다.