There are $n$ earthworms in the earthworm kindergarten. For easier management, the kindergarten director, "God Blade," often has these earthworms line up for performances.

All earthworms are numbered with consecutive positive integers from $1$ to $n$. The length of each earthworm can be represented by a positive integer. According to the admission requirements, the length of every earthworm does not exceed $6$. God Blade wants these earthworms to form several queues. Initially, each earthworm forms its own queue consisting of only one earthworm, which is both at the head and the tail of the queue.

God Blade will perform $m$ operations in sequence. Each operation is one of the following three types:

1. Given $i$ and $j$, merge the two queues containing earthworm $i$ and earthworm $j$ into one queue. Specifically, place earthworm $j$ immediately after earthworm $i$, while the relative order of all other earthworms in the queues remains unchanged.
2. Given $i$, separate earthworm $i$ and the earthworm immediately following it into two queues. Specifically, after the separation, earthworm $i$ is at the tail of one queue, and the earthworm that was immediately following it is at the head of the other queue. The relative order of all other earthworms remains unchanged.
3. Given a positive integer $k$ and a digit string $s$ with length at least $k$, for every consecutive substring $t$ of $s$ with 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 earthworm queues, define the "backward $k$-digit string" of an earthworm as: starting from this earthworm, follow the direction of the queue to find the nearest $k$ earthworms (including itself), and treat the lengths of these earthworms as a digit string formed by concatenation. If fewer than $k$ earthworms are found, the earthworm does not have a "backward $k$-digit string." $f(t)$ represents the number of earthworms whose "backward $k$-digit string" is exactly $t$.

Input

Read data from the file queue.in. The first line 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 not exceeding $6$, representing the lengths of earthworms $1, 2, \dots, n$ in order. The next $m$ lines each describe an operation. Each operation can be in the format: 1 i j ($1 \le i, j \le n$): Merge the two queues containing earthworm $i$ and earthworm $j$. In the new queue, earthworm $j$ is immediately after earthworm $i$. It is guaranteed that before this operation, earthworm $i$ is at the tail of a queue, earthworm $j$ is at the head of a queue, and the two earthworms are in different queues. 2 i ($1 \le i \le n$): Separate earthworm $i$ and the earthworm immediately following it into two queues. It is guaranteed that before this operation, earthworm $i$ is not at the tail of a queue. * 3 s k ($k$ is a positive integer, $s$ is a digit string of length at least $k$): Query the product of $f(t)$ for every substring $t$ of $s$ with length $k$, modulo $998244353$.

Adjacent elements on the same line are separated by exactly one space. The input file may be large; please do not use slow input methods.

Output

Output to the file queue.out. For each operation of the form 3 s k, output one line containing a single integer representing the result of the query.

Subtasks

It is guaranteed that $n \le 2 \times 10^5$, $m \le 5 \times 10^5$, $k \le 50$. Let $\sum |s|$ be the sum of lengths of all query strings $s$ in an input file, then $\sum |s| \le 10^7$. Let $c$ be the number of operations of the form 2 i in an input file, then $c \le 10^3$.

If the "All 1s" column for a test case is "Yes", it means all earthworms in that test case have a length of 1, and every digit of all query strings $s$ is also 1. Cells covered by a merge from above are empty.

Examples

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

Output 1

0
81
1
81
0

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

Output 2

64
1
0
75497471
1
0
75497471