P3823 [NOI2017] Earthworms Queueing

There are $n$ earthworms in a kindergarten. For easier management, the principal Shen Dao Shou often asks the earthworms to line up and perform. All earthworms are numbered with consecutive positive integers from $1$ to $n$. The length of each earthworm is a positive integer, and by admission requirements, all lengths do not exceed $6$. Shen Dao Shou wants these earthworms to form several queues. Initially, each earthworm forms a queue by itself, where that earthworm is both the head and the tail of its queue. Shen Dao Shou 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 earthworms $i$ and $j$ into a single queue. Specifically, place earthworm $j$ immediately after earthworm $i$, and keep the relative order of all other earthworms unchanged. 2. Given $i$, split earthworm $i$ and the earthworm immediately after it into two queues. Specifically, after the split, earthworm $i$ becomes the tail of one queue, and the earthworm that was immediately after it becomes 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$ of length at least $k$, for every length-$k$ contiguous substring $t$ of $s$ (there are $|s|-k+1$ such substrings, where $|s|$ is the length of $s$), define a function $f(t)$ and ask for the product of all these $f(t)$ values modulo $998244353$. The definition of $f(t)$ is as follows: For the current queues of earthworms, define an earthworm’s backward $k$-digit string as follows: starting from that earthworm and moving along the queue towards the back, find the nearest $k$ earthworms (including itself) and concatenate their lengths as characters to form a digit string. If fewer than $k$ earthworms can be found this way, then it does not have a backward $k$-digit string. For example, if the queue of earthworms has earthworm $10$ at the head, followed by earthworm $22$, followed by earthworm $3$ (which is at the tail), and their lengths are $4$, $5$, and $6$ respectively, then the backward $3$-digit string of earthworm $10$ is `456`. Earthworm $22$ does not have a backward $3$-digit string, but its backward $2$-digit string is `56`, and its backward $1$-digit string is `5`. Then $f(t)$ denotes the number of earthworms whose backward $k$-digit string is exactly $t$.

The first line contains two positive integers $n, m$, denoting the number of earthworms and the number of operations. The second line contains $n$ positive integers not exceeding $6$, in order, denoting the lengths of earthworms numbered $1, 2, \dots, n$. Each of the next $m$ lines describes an operation, in one of the following formats: - `1` $i$ $j$ ($1 \leq i, j \leq n$): Merge the two queues containing earthworms $i$ and $j$ into one queue, and in the new queue, place earthworm $j$ immediately after earthworm $i$. It is guaranteed that before this operation, earthworm $i$ is at the tail of some queue, earthworm $j$ is at the head of some queue, and the two earthworms are not in the same queue. - `2` $i$ ($1 \leq i \leq n$): Split earthworm $i$ and the earthworm immediately after it into two queues. It is guaranteed that before this operation, earthworm $i$ is not the tail of its queue. - `3` $s$ $k$ ($k$ is a positive integer, and $s$ is a digit string of length at least $k$): Query the product of $f(t)$ over every length-$k$ substring $t$ of $s$, modulo $998244353$. The definition of $f(t)$ is given in the problem statement. Adjacent elements on the same line are separated by exactly one space. The input file can be large. Please avoid overly slow input methods.

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

Constraints: It is guaranteed that $n \leq 2 \times 10^{5}$, $m \leq 5 \times 10^{5}$, $k \leq 50$. Let $\sum |s|$ be the total length of all query strings $s$ in an input file. Then $\sum |s| \leq 10^{7}$. Let $c$ be the number of operations of the form `2 i` in an input file. Then $c \leq 10^{3}$. Details for each test point are shown in the table below: | Test Point | $n$ | $m$ | $k$ | $\sum |s|$ | $c$ | All are $\texttt{1}$ | |:-:|:-:|:-:|:-:|:-:|:-:|:-:| | 1 | $=1$ | $\leq 10^{3}$ | $=1$ | $\leq 10^{3}$ | $=0$ | No | | 2 | $\leq 20$ | $\leq 40$ | $\leq 10$ | $\leq 10^{3}$ | $=0$ | No | | 3 | $\leq 150$ | $\leq 2,000$ | $\leq 50$ | $\leq 10^{3}$ | $\leq 10^{3}$ | No | | 4 | $\leq 500$ | $\leq 600$ | $\leq 50$ | $\leq 10^{3}$ | $=0$ | No | | 5 | $\leq 10^{3}$ | $\leq 2,000$ | $\leq 50$ | $\leq 10^{3}$ | $\leq 10^{3}$ | No | | 6 | $\leq 5 \times 10^{4}$ | $\leq 6 \times 10^{4}$ | $\leq 5$ | $\leq 5 \times 10^{4}$ | $\leq 10^{3}$ | No | | 7 | $\leq 5 \times 10^{4}$ | $\leq 6 \times 10^{4}$ | $\leq 50$ | $\leq 5 \times 10^{4}$ | $=0$ | Yes | | 8 | $\leq 5 \times 10^{4}$ | $\leq 6 \times 10^{4}$ | $\leq 50$ | $\leq 5 \times 10^{4}$ | $=0$ | No | | 9 | $\leq 5 \times 10^{4}$ | $\leq 6 \times 10^{4}$ | $\leq 50$ | $\leq 5 \times 10^{4}$ | $\leq 10^{3}$ | No | | 10 | $\leq 5 \times 10^{4}$ | $\leq 8 \times 10^{4}$ | $\leq 50$ | $\leq 2.5 \times 10^{6}$ | $=0$ | No | | 11 | $\leq 5 \times 10^{4}$ | $\leq 8 \times 10^{4}$ | $\leq 50$ | $\leq 2.5 \times 10^{6}$ | $\leq 10^{3}$ | No | | 12 | $\leq 10^{5}$ | $\leq 1.1 \times 10^{5}$ | $\leq 6$ | $\leq 10^{5}$ | $\leq 10^{3}$ | No | | 13 | $\leq 10^{5}$ | $\leq 1.1 \times 10^{5}$ | $\leq 50$ | $\leq 10^{5}$ | $=0$ | Yes | | 14 | $\leq 10^{5}$ | $\leq 1.1 \times 10^{5}$ | $\leq 50$ | $\leq 10^{5}$ | $=0$ | No | | 15 | $\leq 10^{5}$ | $\leq 1.1 \times 10^{5}$ | $\leq 50$ | $\leq 10^{5}$ | $\leq 10^{3}$ | No | | 16 | $\leq 10^{5}$ | $\leq 1.5 \times 10^{5}$ | $\leq 50$ | $\leq 5 \times 10^{6}$ | $=0$ | No | | 17 | $\leq 10^{5}$ | $\leq 1.5 \times 10^{5}$ | $\leq 50$ | $\leq 5 \times 10^{6}$ | $\leq 10^{3}$ | No | | 18 | $\leq 2 \times 10^{5}$ | $\leq 5 \times 10^{5}$ | $=1$ | $\leq 10^{7}$ | $=0$ | No | | 19 | $\leq 2 \times 10^{5}$ | $\leq 5 \times 10^{5}$ | $=1$ | $\leq 10^{7}$ | $\leq 10^{3}$ | No | | 20 | $\leq 2 \times 10^{5}$ | $\leq 2.5 \times 10^{5}$ | $\leq 7$ | $\leq 2 \times 10^{5}$ | $\leq 10^{3}$ | No | | 21 | $\leq 2 \times 10^{5}$ | $\leq 2.5 \times 10^{5}$ | $\leq 50$ | $\leq 2 \times 10^{5}$ | $=0$ | Yes | | 22 | $\leq 2 \times 10^{5}$ | $\leq 2.5 \times 10^{5}$ | $\leq 50$ | $\leq 2 \times 10^{5}$ | $=0$ | No | | 23 | $\leq 2 \times 10^{5}$ | $\leq 2.5 \times 10^{5}$ | $\leq 50$ | $\leq 2 \times 10^{5}$ | $\leq 10^{3}$ | No | | 24 | $\leq 2 \times 10^{5}$ | $\leq 3 \times 10^{5}$ | $\leq 50$ | $\leq 10^{7}$ | $=0$ | No | | 25 | $\leq 2 \times 10^{5}$ | $\leq 3 \times 10^{5}$ | $\leq 50$ | $\leq 10^{7}$ | $\leq 10^{3}$ | No | If the “All are `1`” column of a test point is “Yes”, it means all earthworms have length $1$, and every digit in every query string $s$ is also `1`. Translated by ChatGPT 5