Problem Description

In the Earthworm Kindergarten, there are $n$ earthworms. The principal, Divine Blade, manages them by organizing them into queues for convenience.

All earthworms are numbered consecutively from $1$ to $n$. Each earthworm's length is represented by a positive integer, and by入园 requirement, all earthworms' lengths do not exceed $6$. Divine Blade wants these earthworms to form several queues. Initially, each earthworm forms a queue by itself, being both the head and the tail of the queue.

Divine Blade will perform $m$ operations sequentially, each of which is one of the following three types:

1. Given $i$ and $j$, merge the two queues that $i$-th and $j$-th earthworms belong to into one queue. Specifically, place the $j$-th earthworm immediately after the $i$-th earthworm, maintaining the relative order of the other earthworms.

2. Given $i$, split the queue at the $i$-th earthworm into two queues. Specifically, after the split, the $i$-th earthworm is at the tail of one queue, and the earthworm immediately following it is at the head of the other queue, maintaining the relative order of the other earthworms.

3. Given a positive integer $k$ and a numeric string $s$ of length at least $k$, for each contiguous substring $t$ of $s$ of length $k$ (there are $|s|-k+1$ such substrings, where $|s|$ is the length of $s$), define a function $f(t)$, and query the product of all these $f(t)$ values modulo $998244353$. The definition of $f(t)$ is as follows:

For the current queue of earthworms, define the backward $k$ numeric string of a certain earthworm as: starting from this earthworm, moving backward in the queue, find the nearest $k$ earthworms (including itself), and concatenate their lengths as a numeric string; if fewer than $k$ earthworms are found, it has no backward $k$ numeric string. For example, if the queue is such that the $10$-th earthworm is at the head, followed by the $22$-th earthworm, followed by the $3$-th earthworm (at the tail), and their lengths are $4$, $5$, and $6$ respectively, then the backward $3$ numeric string of the $10$-th earthworm is 456, the $22$-th earthworm has no backward $3$ numeric string, but its backward $2$ numeric string is 56, and its backward $1$ numeric string is 5.

And $f(t)$ represents the number of earthworms whose backward $k$ numeric string exactly matches $t$.

Input Format

The first line of the input file contains two positive integers $n$ and $m$, representing the number of earthworms and the number of operations, respectively.

The second line contains $n$ positive integers, each no more than $6$, representing the lengths of the earthworms numbered from $1$ to $n$.

The next $m$ lines each describe an operation. The format of each operation can be:

• 1 $i$ $j$ ($1 \leq i, j \leq n$) indicates: merging the two queues that the $i$-th and $j$-th earthworms belong to into one queue, with the $j$-th earthworm immediately following the $i$-th earthworm. It is guaranteed that before this operation, the $i$-th earthworm is at the tail of a queue, the $j$-th earthworm is at the head of a queue, and they are not in the same queue.

• 2 $i$ ($1 \leq i \leq n$) indicates: splitting the queue at the $i$-th earthworm into two queues. It is guaranteed that before this operation, the $i$-th earthworm is not at the tail of a queue.

• 3 $s$ $k$ ($k$ is a positive integer, $s$ is a numeric string of length at least $k$) indicates: querying the product of $f(t)$ for each substring $t$ of $s$ of length $k$, modulo $998244353$. The definition of $f(t)$ is as described in the problem statement.

Elements in the same line of the input are separated by exactly one space.

The input file may be large, so do not use excessively slow input methods.

Output Format

For each operation of the form 3 s k, output a line containing a single integer, which is the result of the query.

Sample Input and Output

Sample Input #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

Sample Output #1

0
81
1
81
0

Sample Input #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

Sample Output #2

64
1
0
75497471
1
0
75497471

Notes/Hints

It is guaranteed that $n \leq 2 \times 10^{5}$, $m \leq 5 \times 10^{5}$, and $k \leq 50$.

Let $\sum |s|$ be the sum of the lengths of all $s$ in the input file, then $\sum |s| \leq 10^{7}$.

Let $c$ be the number of operations of the form 2 i in the input file, then $c \leq 10^{3}$.

Detailed information for each test case is provided in the table below:

If a test case's "All 1s" column is "Yes", it means all earthworms' lengths are 1, and all query strings $s$ consist entirely of 1s.

见题面 Input 部分

见题面 Output 部分