题目描述

YDC将给你 $n$ 个字符串，并要求进行 $q$ 次操作，每次操作形如一下四种：

1. 在第 $x$ 个字符串后面加上一个字符 $y$。

2. 询问在第 $k$ 个操作过后的第 $y$ 个字符串在当前的第 $x$ 个字符串中的出现次数。

3. 将第 $x$ 个字符串改成第 $y$ 个字符串。

4. 读入一个字符串，询问它在 $n$ 个串中每一个串中的出现次数。

这里的出现次数是特殊定义的，比如说询问串 $s1$ 中 $s2$ 的出现次数，那么询问时会给出参数 $l,r$，需要回答 $s1$ 有多少子串形如 $a+s2$（'$+$'号代表字符串连接），其中 $a$ 是一个字符集中在第 $[l,r]$ 中的字符。不同的询问所给出的 $l,r$ 可能不同。

另外输入文件可能被加密。

输入格式

第一行三个整数数，$n,m,ty$，分别表示字符串个数，字符集大小，以及是否数据是否被加密，如果数据被加密，则 $ty$ 的值为 $1$，否则为 $0$。

如果数据被加密，令 $lastans$ 为当前操作之前最后一个输出的数（如果此前没有输出则 $lastans=0$）。那么当前操作中读入的所有数均被加密成了原数异或上 $lastans$（即假设原数为 $x$，你读入的数将是 $x^lastans$）。

接下来 $n$ 行，第 $i$ 行将给出第 $i$ 个字符串。字符串将按照如下格式给出：第一个数 $len$ 表示字符串的长度，接下来 $len$ 个整数，两两之间用空格隔开，表示每个位置上的字符是字符集中的第几个（从 $0$ 开始标号）。

再读入一个数 $q$，即操作数。

接着 $q$ 行，每行为一个操作的信息。每行第一个数为操作的类型。

如果是操作 $0$，那么接着两个整数 $x,y$，含义如题所示。

如果是操作 $1$，那么接着五个整数 $x,y,k,l,r$，其中 $l,r$表示出现次数中所要求的 $l,r$。（当 $k=0$ 时表示所有操作进行之前）。

如果是操作 $2$，那么接着两个整数 $x,y$，含义如题所示。

如果是操作 $3$，那么接着两个整数 $l,r$ 和一个字符串 $s$，字符串的格式和上述相同。

输出格式

对于每一个操作 $1$ 和 $3$，你都需要输出他们的答案。你需要确保你的输出顺序与读入顺序一致。

3 3 0
5 0 1 1 1 2
1 1
2 1 1
4
0 1 1
3 0 1 1 1
2 2 1
1 1 2 0 0 1

3 0 1
3

数据范围

对于 $100\%$ 的数据，$2\le n\le 5,1\le m\le 10^5,0\le q\le 2*10^5$。

初始 $n$ 个串的总长度不超过 $2*10^5+20$。

操作 $3$ 中读入的串总长度不超过 $10^6$。

保证数据合法。

保证任意时刻出现的 $n$ 个串均是一个长度不超过 $4*10^5$ 的字符串的子串。

对于前 $30$ 的数据，保证 $q\le 1000$,初始n个串的总长度不超过 $1000+20$，操作 $3$ 中读入的串总长度不超过 $10^4$。

对于前 $60$ 的数据，保证所有的 $l=0,r=m-1$。

对于前 $80$ 的数据，保证数据没有被加密。