由于BubbleCup XI任务的宇航员完成了月球任务,并且是著名歌手的忠实粉丝,他们决定在返回地球之前度过一些愉快的时光,因此创造了一个所谓的“月球漫步挑战”游戏。
宇航员团队获得了月球上陨石坑的地图,以及从一些陨石坑到其他陨石坑的直接双向路径,这些路径对于“月球漫步”是安全的。每条直接路径都以一种颜色着色,并且每两个陨石坑之间都有独特的路径。游戏的目标是找到两个陨石坑,使得给定的颜色数组大多数时候作为连续子数组出现在这两个陨石坑之间的路径上(应该计算重叠的外观)。
为了帮助您最喜欢的球队获胜,您应该编写一个程序,在给定地图的情况下,回答以下类型的查询:对于两个陨石坑和颜色数组,回答给定数组在从第一个陨石坑到第二个陨石坑的路径上作为连续子数组出现的次数。
颜色以小写英文字母表示。
输入
在第一行中,整数 $$$N$$$ $$$(2 \leq N \leq 10^5)$$$ — 月球上的陨石坑数量。陨石坑用数字 $$$1$$$ 到 $$$N$$$ 进行编号。
在接下来的 $$$N-1$$$ 行中,三个值 $$$u, v, L$$$ $$$(1 \leq u, v \leq N, L \in \{a, ..., z\})$$$ — 表示在陨石坑 $$$u$$$ 和 $$$v$$$ 之间有一条颜色为 $$$L$$$ 的直接路径。
下一行包含整数 $$$Q$$$ $$$(1 \leq Q \leq 10^5)$$$ — 查询数。
接下来的 $$$Q$$$ 行包含三个值 $$$u, v$$$ $$$(1 \leq u, v \leq N)$$$ 和 $$$S$$$ $$$(|S| \leq 100)$$$,其中 $$$u$$$ 和 $$$v$$$ 是两个陨石坑,您应该找到它们的颜色数组的次数$$$S$$$(表示为字符串)出现在从 $$$u$$$ 到 $$$v$$$ 的路径上。
输出
对于每个查询输出一个数字,表示从 $$$u$$$ 到 $$$v$$$ 的路径上数组 S 出现的次数。
示例
输入 #1
6 2 3 g 3 4 n 5 3 o 6 1 n 1 2 d 7 1 6 n 6 4 dg 6 4 n 2 5 og 1 2 d 6 5 go 2 3 g
输出 #1
1 1 2 0 1 1 1