题目背景

本来这里应该有一段一脉相承的背景故事。但是因为福尔魔斯验题的时候写吐了，所以背景故事没了。

题目描述

给出 $m$ 个数组 $s_1, s_2, \cdots s_m$ 和一个长为 $n$ 的数组 $t$。

定义 $f(l,r)$ 表示在所有 "把 $t_l...t_r$ 分成若干段，要求每一段都是 $s$ 中某个数组的子段" 的方式中，划分段数的最小值。

有以下操作：

1. 强制限定 $p,p+1$ 处必须划分，如果已经有了则取消。

2. 将 $t$ 的区间 $[l, r]$ 改成数组 $a$，会给出 $a$，每次的 $a$ 可能不一样。

3. 询问 $f(l,r)$，保证有解。

请你完成这些操作。

输入格式

第一行四个数，$n,m,q,id$，表示 $t$ 的长度，总共有多少个文本数组 $s$，操作数，以及数据类型（参见说明）。

接下来 $m$ 行，每行先给出一个数 $k$，代表 $s_i$ 的长度，然后 $k$ 个数给出 $s_i$ 这个数组的元素。

下一行，给出 $n$ 个数，表示 $t$ 中的元素。

接下来 $q$ 行，每行表示一个操作，分别如下：

1. $1\ x$，表示若 $x,x+1$ 处不必须划分，则标为必须划分，否则取消。

2. $2\ l\ r\ a_1\ a_2 \cdots a_{r-l+1}$，表示令 $\forall l \le i \le r，t_i = a_{i-l+1}$。

3. $3\ l\ r$，表示询问 $f(l,r)$。

输出格式

对于每次询问，输出一个数表示答案。每个答案占一行。

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

3
4
5
4

10 5 20 0
3 1 2 3 
5 3 3 1 1 3 
10 1 2 1 1 2 3 2 1 1 3 
2 1 1 
2 1 3 
1 3 2 3 3 1 3 3 2 3 
1 4
2 7 7 3 
3 3 9
1 4
1 2
2 5 5 2 
1 2
2 7 7 2 
1 1
3 5 8
2 4 4 1 
3 3 8
1 1
1 3
2 6 6 1 
2 1 1 1 
2 4 4 2 
1 7
3 1 5
3 1 9

4
2
3
4
6

提示

样例解释

对于第一组样例，初始数组为 $[2,3,3,2,1]$ ，段数最小分割的方式为 $[2,3|3,2|1]$ ，故输出 $3$ 。然后限制了 $3,4$ 之间必须分割，故最小的分割方式为 $[2,3|3|2|1]$ ，输出为 $4$ 。之后数组被修改为 $[2,1,3,2,1]$ ，段数最小的分割方式为 $[2|1|3|2|1]$ ，故输出 $5$ 。最后取消了 $3,4$ 之间必须分割的限制，最小分割方式为 $[2|1|3,2|1]$ ，输出 $4$ 。

数据范围

记 $\sum\limits_{i=1}^m |s_i|= M$ ，对于所有操作 2， $\sum\limits_{i=1}^t |r_i-l_i+1| = T$ ，其中 $t$ 是操作 2 的出现次数， $V$ 为数组中和修改后的数组中的元素的最大值，则各数据点的限制如下：

对于所有数据，保证 $1\le n,M,q\le10^5, 0\le T\le 10^5,1\le V\le10^9, 1\le id\le9, l\le r$ 。$a,t$ 中的所有数都在 $s$ 中出现。

保证给出的数组随机，但是询问的区间与询问的操作并不随机。具体而言，初始给出的 $s,t$ 以及询问时可能给出的 $a$ 在符合上文所述限制之下的所有可能情况中等概率选取。而其他数据则不是随机的。