题目描述

蚯蚓幼儿园有n只蚯蚓。幼儿园园长神刀手为了管理方便，时常让这些蚯蚓们列队表演。

所有蚯蚓用从1到n的连续正整数编号。每只蚯蚓的长度可以用一个正整数表示，根据入园要求，所有蚯蚓的长度都不超过6。神刀手希望这些蚯蚓排成若干个队伍，初始时，每只蚯蚓各自排成一个仅有一只蚯蚓的队伍，该蚯蚓既在队首，也在队尾。

神刀手将会依次进行m次操作，每个操作都是以下三种操作中的一种：

1、给出 i和j，令 i 号蚯蚓与j 号蚯蚓所在的两个队伍合并为一个队伍，具体来说，令j 号蚯蚓紧挨在 i号蚯蚓之后，其余蚯蚓保持队伍的前后关系不变。
2、给出 i，令 i 号蚯蚓与紧挨其后的一只蚯蚓分离为两个队伍，具体来说，在分离之后，i 号蚯蚓在其中一个队伍的队尾，原本紧挨其后的那一只蚯蚓在另一个队伍的队首，其余蚯蚓保持队伍的前后关系不变。
3、给出一个正整数 k 和一个长度至少为 k 的数字串 s，对于 s 的每个长度为 k 的连续子串 t（这样的子串共有|s|−k+1 个，其中|s| 为 s 的长度），定义函数 f(t)，询问所有这些 f(t) 的乘积对998244353 取模后的结果。其中 f(t) 的定义如下：
对于当前的蚯蚓队伍，定义某个蚯蚓的向后 k 数字串为：从该蚯蚓出发，沿队伍的向后方向，寻找最近的 k 只蚯蚓（包括其自身），将这些蚯蚓的长度视作字符连接而成的数字串；如果这样找到的蚯蚓不足 k 只，则其没有向后 k 数字串。例如蚯蚓的队伍为 10 号蚯蚓在队首，其后是 22 号蚯蚓，其后是 3 号蚯蚓（为队尾），这些蚯蚓的长度分别为 4、5、6，则 10 号蚯蚓的向后 3 数字串为 456， 22 号蚯蚓没有向后 3 数字串，但其向后 2 数字串为 56，其向后 1 数字串为 5。

而 f(t) 表示所有蚯蚓中，向后 k 数字串恰好为 t 的蚯蚓只数。

输入格式

从标准输入读入数据。
输入文件的第一行有两个正整数 n,m，分别表示蚯蚓的只数与操作次数。
第二行包含 n 个不超过 6 的正整数，依次表示编号为 1,2,…,n 的蚯蚓的长度。
接下来 m行，每行表示一个操作。每个操作的格式可以为：
* 1 i j（1≤i,j≤n）表示：令 i 号与 j 号蚯蚓所在的两个队伍合并为一个队伍，新队伍中， j 号蚯蚓紧挨在 i 号蚯蚓之后。保证在此操作之前， i 号蚯蚓在某个队伍的队尾， j 号蚯蚓在某个队伍的队首，且两只蚯蚓不在同一个队伍中。
* 2 i（1≤i≤n）表示：令 i 号蚯蚓与紧挨其后一个蚯蚓分离为两个队伍。保证在此操作之前， i 号蚯蚓不是某个队伍的队尾。
* 3 s k（k 为正整数，s 为一个长度至少为 k 的数字串）表示：询问 s 的每个长度为 k 的子串 t 的f(t) 的乘积，对 998244353 取模的结果。 f(t) 的定义见题目描述。
同一行输入的相邻两个元素之间，用恰好一个空格隔开。

输入文件可能较大，请不要使用过于缓慢的读入方式。

输出格式

输出到标准输出。
依次对于每个形如 3 s k 的操作，输出一行，仅包含一个整数，表示询问的结果。

Sample 1

输入样例1

5 9
3 1 3 5 3
3 333135 2
3 333135 1
1 1 3
1 2 5
1 3 2
1 5 4
3 333135 2
3 333135 1
3 333135 3

输出样例1

0
81
1
81
0

样例1解释

第一次询问：由于每个队伍均只有一只蚯蚓，所以没有任何蚯蚓有向后 22 数字串，答案为 f(33)×f(33)×f(31)×f(13)×f(35)=0×0×0×0×0=0.
第二次询问：每个队伍仍只有一只蚯蚓，每只蚯蚓的向后 11 数字串就是将自己的长度视为字符的数字串，即：得到的 55 个向后 11 数字串为 1、3、3、3、5（不分先后顺序，下同），答案为 f(3)×f(3)×f(3)×f(1)×f(3)×f(5)=3×3×3×1×3×1=81。
接下来进行了若干次队伍的合并操作，使得所有蚯蚓合并成了一个队伍，这个队伍从前到后的蚯蚓依次为： 1 号蚯蚓（长度为 3 ）、3 号蚯蚓（长度为 3 ）、2 号蚯蚓（长度为 1 ）、5号蚯蚓（长度为3 ）、4号蚯蚓（长度为 5 ）。
第三次询问： 4号蚯蚓没有向后2 数字串，而其他蚯蚓都有。得到的4 个向后 2数字串为 13、31、33、35，答案为 f(33)×f(33)×f(31)×f(13)×f(35)=1×1×1×1×1=1.
第四次询问：虽然队伍的排列方式改变了，但是每只蚯蚓的向后 11 数字串没有发生改变，所以答案同第二次询问。
第五次询问： 44 号蚯蚓、55 号蚯蚓没有向后 33 数字串，而其他蚯蚓都有。得到的 33 个向后 33 数字串为 135、331、313，答案为 f(333)×f(331)×f(313)×f(135)=0×1×1×1=0。

样例2

输入样例2

2 10
6 6
3 666666 1
1 1 2
3 666666 2
3 666666 4
3 666666666666666666666666666666 1
2 1
1 2 1
3 666666 2
3 666666 4
3 666666666666666666666666666666 1

输出样例2

64
1
0
75497471
1
0
75497471

样例2解释

对于第四次、第七次询问，输入的 s 为 30 个字符 6，所有 f(t) 的乘积是 2^30=1073741824，输出的结果是这个数对于998244353 取模的结果。

限制与约定、样例数据下载：

http://uoj.ac/problem/315