题目描述

给定一棵树，树上的每条边上有一个字符。给定一个常数 $X$。

有两种操作，每次操作输入三个整数与一个字符串：

1 x y S：对于 $x$ 到 $y$ 的有向简单路径上的边，将路径上的第 $i$ 条边上的字符替换为 $S$ 上的对应字符 $S_i$，保证这条 $x$ 到 $y$ 之间路径的边数为 $X$。

2 x y S：查询 $x$ 到 $y$ 构成的有向简单路径所形成的字符串上，$S$ 匹配的次数（这里的匹配即：将 $S$ 当做模式串，在这条路径构成的字符串上逐位置匹配。）例如：$S=121$ ，路径上的字符串为 $1212122$，则匹配了2次，分别在第 $[1,3]$ 处和$[3,5]$ 处。

上述所有字符串 $S$ 的下标从 $1$ 开始，保证每个输入的字符串长度均为 $X$。

输入格式

第一行三个以空格分隔的整数 $n,m,X$。

之后一行包含 $n-1$ 个数，第 $i$ 个数表示第 $i+1$ 个点的父亲 $f_{i+1}$，保证每个点父亲的编号比这个点的编号小。

之后一行包含 $n-1$ 个字符，第 $i$ 个字符表示第 $i+1$ 个点到父亲的边上的字符 $a_{i+1}$。

之后 $m$ 行，每行输入以空格隔开的三个整数 $opt,x,y$ 与一个长为 $X$ 的字符串 $S$，表示一次操作。

输出格式

若干行，每行一个整数，表示每次 $2$ 操作的答案。

样例

输入

10 7 2
1 2 3 2 3 3 3 3 7
212111121
2 1 4 21
1 10 3 21
1 9 7 22
2 2 10 12
2 6 8 11
1 9 8 12
2 4 7 11

输出

1
1
1
0

子任务

对于 $10\%$ 的数据，满足 $1\le n,m\le 250$。

对于另外 $10\%$ 的数据，不存在 1 操作。

对于另外 $10\%$ 的数据，满足 $X=1$。

对于另外 $10\%$ 的数据，满足 $X\le 3$。

对于另外 $10\%$ 的数据，满足 $X\ge 20000$。

对于另外 $10\%$ 的数据，满足 $f_i=i-1$。

对于另外 $10\%$ 的数据，满足 $a_i\le 1$。

对于另外 $10\%$ 的数据，满足 $1\le n,m\le 2.5\times 10^4$，$mX\le 2.5\times 10^4$。

对于另外 $10\%$ 的数据，满足 $1\le n,m\le 2.5\times 10^5$，$mX\le 2.5\times 10^5$。

对于 $100\%$ 的数据，满足 $1\le n,m,X\le 5\times 10^5$，字符集为 $[1,9]$ 以内的整数，$mX\le 5\times 10^5$。