Queue

There are $n$ worms numbered from $1$ to $n$. The length of each worm is a positive integer between $1$ and $6$. You want to arrange the worms into several queues. Initially, each worm is alone in its own queue. Each worm is both the front and the end of its queue.

There are $m$ operations. Each operation is one of the following three types:

• 1 i j ($1 \leq i,j \leq n$): Merge the queue that contains worm $i$ with the queue that contains worm $j$. In the new queue, worm $j$ immediately follows worm $i$. Every other worm keeps its neighbors. It is guaranteed that worm $i$ is at the tail of its queue, worm $j$ is at the front of its queue, and $i$ and $j$ are not in the same queue.
• 2 i ($1 \leq i \leq n$): Split the queue between worm $i$ and the worm right after it. It is guaranteed that worm $i$ is not at the tail of its queue.
• 3 s k ($k$ is a positive integer and $s$ is a numeric string with length at least $k$): Find the product of $f(t)$ modulo 998,244,353, taken over all substrings $t$ of length $k$ in $s$. There are $|s|-k+1$ such substrings for given $s$ and $k$.

The value $f(t)$ is defined as follows.

In a given queue, the $k$-string after worm $i$ is formed by starting at worm $i$, walking toward the tail, and taking the $k$ worms closest to $i$, counting $i$ itself. Their lengths are concatenated in order. If fewer than $k$ worms remain before the tail, worm $i$ has no $k$-string. For example, suppose a queue holds worms 10, 22, 3 with lengths 4, 5, 6. The 3-string after worm 10 is 456. Worm 22 has no 3-string, but its 2-string is 56 and its 1-string is 5.

$f(t)$ is the number of worms whose $k$-string is exactly $t$.

The first line contains two positive integers $n$ and $m$, the number of worms and the number of operations. The second line contains $n$ positive integers, each at most 6, giving the lengths of worms $1$ through $n$. Each of the next $m$ lines describes one operation. The input file may be large.

For each operation of type 3 s k, print the answer on its own line.

$n \leq 2 \times 10^5$, $m \leq 5 \times 10^5$, $k \leq 50$.

Let $\sum |s|$ be the sum of the lengths of $s$ over all queries. Then $\sum |s| \leq 10^7$.

Let $c$ be the number of operations of the form 2 i. Then $c \leq 10^3$.