{"raw_statement":[{"iden":"statement","content":"给定一棵树，树上的每条边上有一个字符。给定一个常数 $X$。\n\n有两种操作，每次操作输入三个整数与一个字符串：\n\n`1 x y S`：对于 $x$ 到 $y$ 的有向简单路径上的边，将路径上的第 $i$ 条边上的字符替换为 $S$ 上的对应字符 $S_i$，保证这条 $x$ 到 $y$ 之间路径的边数为 $X$。\n\n`2 x y S`：查询 $x$ 到 $y$ 构成的有向简单路径所形成的字符串上，$S$ 匹配的次数（这里的匹配即：将 $S$ 当做模式串，在这条路径构成的字符串上逐位置匹配。）例如：$S=121$ ，路径上的字符串为 $1212122$，则匹配了2次，分别在第 $[1,3]$ 处和$[3,5]$ 处。\n\n上述所有字符串 $S$ 的下标从 $1$ 开始，保证每个输入的字符串长度均为 $X$。"},{"iden":"input","content":"第一行三个以空格分隔的整数 $n,m,X$。\n\n之后一行包含 $n-1$ 个数，第 $i$ 个数表示第 $i+1$ 个点的父亲 $f_{i+1}$，保证每个点父亲的编号比这个点的编号小。\n\n之后一行包含 $n-1$ 个字符，第 $i$ 个字符表示第 $i+1$ 个点到父亲的边上的字符 $a_{i+1}$。\n\n之后 $m$ 行，每行输入以空格隔开的三个整数 $opt,x,y$ 与一个长为 $X$ 的字符串 $S$，表示一次操作。"},{"iden":"output","content":"共 $m$ 行，每行一个整数，表示每次 $2$ 操作的答案。"},{"iden":"note","content":"Idea：nzhtl1477，Solution：ComeIntoPower&nzhtl1477&ccz181078，Code：ccz181078，Data：ccz181078\n\n对于 $10\\%$ 的数据，满足 $1\\le n,m\\le 250$。\n\n对于另外 $10\\%$ 的数据，不存在 1 操作。\n\n对于另外 $10\\%$ 的数据，满足 $X=1$。\n\n对于另外 $10\\%$ 的数据，满足 $X\\le 3$。\n\n对于另外 $10\\%$ 的数据，满足 $X\\ge 20000$。\n\n对于另外 $10\\%$ 的数据，满足 $f_i=i-1$。\n\n对于另外 $10\\%$ 的数据，满足 $a_i\\le 1$。\n\n对于另外 $10\\%$ 的数据，满足 $1\\le n,m\\le 2.5\\times 10^4$，$mX\\le 2.5\\times 10^4$。\n\n对于另外 $10\\%$ 的数据，满足 $1\\le n,m\\le 2.5\\times 10^5$，$mX\\le 2.5\\times 10^5$。\n\n对于 $100\\%$ 的数据，满足 $1\\le n,m,X\\le 5\\times 10^5$，字符集为 $[1,9]$ 以内的整数，$mX\\le 5\\times 10^5$。"}],"translated_statement":null,"sample_group":[["10 7 2\n1 2 3 2 3 3 3 3 7\n212111121\n2 1 4 21\n1 10 3 21\n1 9 7 22\n2 2 10 12\n2 6 8 11\n1 9 8 12\n2 4 7 11","1\n1\n1\n0"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}