earthwormlines

Earthworms Lining Up

There are \(n\) earthworms in the Earthworm Kindergarten. The director of the kindergarten, 'Swordsman', often has the earthworms perform in lines.

Each earthworm is assigned a number from \(1\) to \(n\). The length of each worm can be expressed as a positive integer, and according to the admission requirements, all worms will be no longer than 6 units. Swordsman wants the earthworms to form up into lines. Initially, each earthworm stands alone in a line of its own.

Swordsman will perform \(m\) operations in sequence, each of which will be one of the following three types:

• 1. Given \(i\) and \(j\), merge the lines of earthworm \(i\) and earthworm \(j\) into one. Specifically, earthworm \(j\) is guaranteed to be at the front of its line and earthworm \(i\) at the back of its own; and the line of earthworm \(j\) is to be placed behind the line of earthworm \(i\).
• 2. Given \(i\), split earthworm \(i\)'s line into two between earthworm \(i\) and the earthworm immediately behind it. In particular, after the separation, earthworm \(i\) will be at the end of one new line, and the earthworm which was behind \(i\) will be at the front of the other line.
• 3. Given an integer \(k\), a digit string \(s\) of length at least \(k\), and a function \(f(t)\), evaluate the product modulo 998244353 of all \(f(t)\) for each substring \(t\) of \(s\) with length \(k\) (There are \(|s| - k + 1\) such substrings, where \(|s|\) is the length of \(s\)). \(f(t)\) is defined as follows:

For the current alignment of earthworms, the \(k\)-line sequence of a worm is the digit string obtained by concatenating the length of the earthworm, with the length of the earthworm behind it in its line, then the length of the earthworm behind that and so on for \(k\) earthworms in total. If for an earthworm there are less than \(k - 1\) worms behind it, then that earthworm has no \(k\)-line sequence.

For example, suppose earthworm 10 is at the start of a line, followed by earthworm 22, followed by earthworm 3 at the end of the line; and these earthworms have lengths 4, 5, and 6 respectively. Then, earthworm 10 has a 3-line sequence of 456; and earthworm 22 has no 3-line sequence, but has a 2-line sequence of 56 and a 1-line sequence of 5.

Given these definitions, \(f(t)\) is the total number of earthworms with a \(|t|\)-line sequence identical to \(t\).

Limits

\(1 \leq n \leq 2 \times 10^5\), \(1 \leq m \leq 5 \times 10^5\), \(1 \leq k \leq 50\).
Let S be the sum of lengths of all digit strings \(s\) in type 3 operations. \(S \leq 10^7\).
No more than 1000 operations of type 2 will occur within any testcase.

Subtask #	Score	Constraints
1	12	\(n \leq 150\) \(m \leq 2000\) \(S \leq 1000\)
2	8	\(n \leq 1000\) \(m \leq 2000\) \(S \leq 1000\)
3	24	\(n \leq 5 \times 10^4\) \(m \leq 8 \times 10^4\) \(S \leq 2.5 \times 10^6\)
4	16	\(k \leq 7\)
5	16	\(S \leq 2 \times 10^5\)
6	24	No additional constraints

Input format

The first line of input consists of two integers \(n\) and \(m\), the number of earthworms and the number of operations respectively.
The second line of input consists of \(n\) positive integers, the lengths of earthworms \(1\) to \(n\). These integers will be no larger than \(6\).
\(m\) lines follow. Each line represents one operation, of one of the following three formats:

• \(1\) \(i\) \(j\): Merge the lines of earthworm \(i\) and earthworm \(j\). Earthworm \(i\) is guaranteed to be at the back of a line and earthworm \(j\) at the front of another.
• \(2\) \(i\): Split a line between earthworm \(i\) and the earthworm behind it. It is guaranteed that earthworm \(i\) is not currently at the back of a line.
• \(3\) \(s\) \(k\): Evaluate the sum modulo 998244353 of \(f(t)\), for every substring \(t\) of \(s\) with length \(k\).

Output format

Output one line for every type 3 operation. Each line should contain a single integer, the answer to the corresponding type 3 operation.

Samples

Sample Input 1	Sample Output 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	0 81 1 81 0

Sample Input 2	Sample Output 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	64 1 0 75497471 1 0 75497471