ydc 很喜欢字符串，他有特别的视角看待字符串。

字符串是由字符组成的。字符一共 $m$ 种，分别编号为 $0, \dots, m-1$。

对于整数 $l, r$，如果两个字符串 $s, t$ 满足在 $s$ 最前面加一个编号在区间 $[l, r]$ 以内的字符后两串相等，那么就称 $s$ 能通过 $[l, r]$ 与 $t$ 相等。

ydc 将给你 $n$ 个字符串，编号为 $1, \dots, n$，并要求进行 $q$ 次操作，每次操作形如以下四种之一：

• 操作0：在第 $x$ 个字符串后面加上一个字符 $c$。保证 $1 \leq x \leq n$，$0 \leq c < m$。
• 操作1：询问当前第 $x$ 个字符串中有多少个子串满足在第 $k$ 个操作过后的第 $y$ 个字符串能通过 $[l, r]$ 与该子串相等。$k$ 是小于当前操作编号的非负整数，$k = 0$ 表示在所有操作之前。保证 $1 \leq x, y \leq n$，$0 \leq l \leq r < m$。
• 操作2：将第 $x$ 个字符串改成第 $y$ 个字符串。保证 $1 \leq x, y \leq n$。
• 操作3：给你一个字符串 $s$，对于这 $n$ 个串中的每个串询问有多少个子串满足 $s$ 能通过 $[l, r]$ 与该子串相等，$0 \leq l \leq r < m$。

另外，输入文件可能被加密来强制你在线进行操作。

输入格式

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

如果数据被加密，令 $\mathrm{lastans}$ 为当前操作之前最后一个输出的数（如果此前没有输出则 $\mathrm{lastans} = 0$）。那么当前操作中读入的所有数均被加密成了原数异或 $\mathrm{lastans}$。

字符串将按照如下格式给出：第一个数为一个正整数 $l$ 表示字符串的长度，后面跟着 $l$ 个整数，两两之间用空格隔开，表示每个位置上的字符编号。

接下来 $n$ 行，第 $i$ 行将给出第 $i$ 个字符串。

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

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

如果是操作0，那么接着两个整数 $x, c$。

如果是操作1，那么接着五个整数 $x,y,k,l,r$。

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

如果是操作3，那么接着两个整数 $l,r$ 和一个字符串 $s$。

输出格式

按照输入顺序回答询问。

对于每个操作1，输出一行一个整数表示答案。

对于每个操作3，输出一行 $n$ 个整数分别表示每个字符串中满足条件的子串个数。

样例一

input

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

output

3 0 1
3

样例二

input

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

output

3 0 1
3

限制与约定

$2 \leq n \leq 5$，$1 \leq m \leq 10^5$，$1 \leq q \leq 2 \times 10^5$。

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

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

保证数据合法。

保证存在一个长度不超过 $4 \times 10^5$ 的字符串使得任意时刻那 $n$ 个串均是它的子串。

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

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

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

时间限制：$5\texttt{s}$

空间限制：$512\texttt{MB}$

来源

中国国家集训队互测2015 - By 刘研绎

下载

样例数据下载