题目描述
给定一棵树,树上的每条边上有一个字符。给定一个常数 X。
有两种操作,每次操作输入三个整数与一个字符串:
1 x y S
:对于 x 到 y 的有向简单路径上的边,将路径上的第 i 条边上的字符替换为 S 上的对应字符 Si,保证这条 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 个点的父亲 fi+1,保证每个点父亲的编号比这个点的编号小。
之后一行包含 n−1 个字符,第 i 个字符表示第 i+1 个点到父亲的边上的字符 ai+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≤n,m≤250。
对于另外 10% 的数据,不存在 1 操作。
对于另外 10% 的数据,满足 X=1。
对于另外 10% 的数据,满足 X≤3。
对于另外 10% 的数据,满足 X≥20000。
对于另外 10% 的数据,满足 fi=i−1。
对于另外 10% 的数据,满足 ai≤1。
对于另外 10% 的数据,满足 1≤n,m≤2.5×104,mX≤2.5×104。
对于另外 10% 的数据,满足 1≤n,m≤2.5×105,mX≤2.5×105。
对于 100% 的数据,满足 1≤n,m,X≤5×105,字符集为 [1,9] 以内的整数,mX≤5×105。