워넘 줄

워넘 $n$마리가 1번부터 $n$번까지 번호가 붙어 있다. 각 워넘의 길이는 1 이상 6 이하의 정수이다. 워넘들을 여러 개의 줄(queue)로 배치하려 한다. 처음에는 각 워넘이 자기 혼자만 있는 줄에 서 있다. 각 워넘은 자기 줄의 맨 앞이자 맨 뒤이다.

연산은 $m$개 주어진다. 연산은 다음 세 가지 중 하나이다.

• 1 i j ($1 \leq i,j \leq n$): 워넘 $i$가 속한 줄과 워넘 $j$가 속한 줄을 합친다. 합쳐진 줄에서 워넘 $j$는 워넘 $i$ 바로 뒤에 온다. 나머지 워넘의 앞뒤 관계는 그대로 유지된다. 워넘 $i$는 어떤 줄의 맨 뒤에 있고, 워넘 $j$는 어떤 줄의 맨 앞에 있으며, $i$와 $j$는 같은 줄에 있지 않다는 것이 보장된다.
• 2 i ($1 \leq i \leq n$): 워넘 $i$와 바로 뒤의 워넘 사이에서 줄을 나눈다. 워넘 $i$는 줄의 맨 뒤가 아니라는 것이 보장된다.
• 3 s k ($k$는 양의 정수이고, $s$는 길이가 $k$ 이상인 숫자 문자열): 길이가 $k$인 $s$의 모든 부분 문자열 $t$에 대해 $f(t)$를 전부 곱한 값을 $998\,244\,353$으로 나눈 나머지를 구한다. $s$와 $k$가 주어지면 이런 부분 문자열은 $|s|-k+1$개이다.

$f(t)$는 다음과 같이 정의한다.

주어진 줄에서 워넘 $i$ 뒤의 $k$-문자열은 $i$에서 시작해 줄의 뒤쪽으로 가면서 $i$를 포함해 $i$에 가장 가까운 워넘 $k$마리를 찾고, 이 워넘들의 길이를 순서대로 이어 붙인 것이다. 줄 끝에 도달하기 전에 워넘이 $k$마리보다 적게 남으면 워넘 $i$는 $k$-문자열을 갖지 않는다. 예를 들어 줄에 워넘 10, 22, 3이 이 순서로 있고 길이가 각각 4, 5, 6이라고 하자. 워넘 10 뒤의 3-문자열은 456이다. 워넘 22에는 3-문자열이 없지만, 2-문자열은 56이고 1-문자열은 5이다.

$f(t)$는 $k$-문자열이 정확히 $t$인 워넘의 수이다.

첫 줄에 워넘의 수 $n$과 연산의 수 $m$이 주어진다. 둘째 줄에는 워넘 1번부터 $n$번까지의 길이가 $n$개의 양의 정수로 주어지며, 각 값은 6 이하이다. 이어서 $m$개의 줄에 연산이 한 줄씩 주어진다. 입력 파일이 클 수 있다.

3 s k 연산마다 답을 한 줄에 하나씩 출력한다.

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

모든 쿼리에서 $s$ 길이의 합을 $\sum |s|$라고 한다. 이때 $\sum |s| \leq 10^7$이다.

2 i 형태의 연산 개수를 $c$라고 한다. 이때 $c \leq 10^3$이다.