Worm Kindergarten Queue Operations

There are \(n\) worms in the Worm Kindergarten, numbered from \(1\) to \(n\). Each worm has a positive integer length not exceeding 6. Initially, every worm forms its own team (thus it is both the head and the tail of its team).

The director will perform \(m\) operations sequentially. Each operation is one of the following three types:

1. Merge Operation: Given two integers \(i\) and \(j\), merge the two teams containing worm \(i\) and worm \(j\) into one team. Specifically, insert the entire team containing worm \(j\) immediately after worm \(i\) in its team while preserving the relative order of worms in both teams.
2. Split Operation: Given an integer \(i\), split the team containing worm \(i\) into two teams by separating worm \(i\) and the worm immediately following \(i\). After the split, worm \(i\) becomes the tail of the first team, and the worm that was immediately after \(i\) becomes the head of the new team. The order in each team remains unchanged.
3. Query Operation: Given a positive integer \(k\) and a digit string \(s\) (with \(|s| \ge k\)), consider every contiguous substring \(t\) of \(s\) with length \(k\) (there are \(|s|-k+1\) such substrings). For a fixed \(k\), define the backward \(k\)-digit string of a worm as the number formed by concatenating the lengths (each as a digit) of the worm and the next \(k-1\) worms in its team. If a worm’s team does not have enough worms (i.e. if it is among the last \(k-1\) worms of its team), then it does not have a backward \(k\)-digit string. For each substring \(t\) of \(s\), define \(f(t)\) as the number of worms whose backward \(k\)-digit string is exactly \(t\). The answer to the query is the product of all these \(f(t)\) values modulo \(998244353\).

Input/Output Format Changes:

You are given the initial configuration and the \(m\) operations. For each Query Operation (type 3), output a single line with the answer.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of worms and the number of operations).

The second line contains \(n\) integers, where the \(i\)-th integer represents the length of worm \(i\) (each length is between 1 and 6 inclusive).

The following \(m\) lines each describe an operation in one of the following formats:

• For a Merge Operation: 1 i j
• For a Split Operation: 2 i
• For a Query Operation: 3 k s where \(s\) is a string of digits with length at least \(k\)

It is guaranteed that all operations are valid.

outputFormat

For each Query Operation (type 3), output a single line containing the answer (the product of \(f(t)\) over all contiguous substrings \(t\) of \(s\) with length \(k\), modulo \(998244353\)).

sample

3 3
1 2 3
3 2 123
1 1 2
3 2 12

0
1