从前有一棵树,树上的每条边上都有一个小写字母。
有 次这样的询问:每次指出树上的两点 并给出一个由小写字母构成的字符串 ,询问串 在 中出现了多少次,其中 表示树上从点 到点 的唯一路径上每条边上的小写字母顺次连接形成的字符串。
注意 。
第一行两个正整数 。
接下来 行,每行两个正整数 和一个小写字母 ,表示一条树边 ,这条树边上的小写字母是 。
接下来 行,每两行表示一次询问。对于每次询问,第一行两个正整数 ,第二行一个由小写字符构成的字符串 ,意义详见题目描述。
输出 行表示每次询问的答案。
见附加文件
记 ,即输入的询问串总长度。
对于 的数据,