$n$마리의 벌레가 있으며, 벌레들은 $1$번부터 $n$번까지 번호가 매겨져 있다. 이때, 각 벌레의 길이는 $1$에서 $6$ 사이의 양의 정수이다. 철수는 벌레들을 여러 개의 줄로 배치하려고 한다. 처음에는 각 벌레가 자기 자신만 있는 줄에 따로 속해 있으며, 각 벌레는 자신이 속한 줄의 맨 앞이자 맨 끝에 있다.
총 $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$ 이상인 숫자 문자열): 문자열 $s$에서 길이 $k$인 모든 연속 부분 문자열 $t$에 대해 $f(t)$의 곱을
$998\,244\,353$로 나눈 나머지를 구한다. 가능한 부분 문자열 $t$는 총 $|s| - k + 1$개이다.
$f(t)$는 다음과 같이 정의된다.
어떤 줄에서 벌레 $i$의 $k$-문자열($k$-string)은 벌레 $i$부터 줄의 끝 방향으로 $k$마리의 벌레 길이를 이어붙인 문자열이다. 만약 $k$개보다 적은 벌레가 있다면 $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$개가 주어진다. 각 값은 $1$ 이상 $6$ 이하이다.
geunyang 1년 전
## 문제
$n$마리의 벌레가 있으며, 벌레들은 $1$번부터 $n$번까지 번호가 매겨져 있다. 이때, 각 벌레의 길이는 $1$에서 $6$ 사이의 양의 정수이다. 철수는 벌레들을 여러 개의 줄로 배치하려고 한다. 처음에는 각 벌레가 자기 자신만 있는 줄에 따로 속해 있으며, 각 벌레는 자신이 속한 줄의 맨 앞이자 맨 끝에 있다.
총 $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$ 이상인 숫자 문자열): 문자열 $s$에서 길이 $k$인 모든 연속 부분 문자열 $t$에 대해 $f(t)$의 곱을
$998\,244\,353$로 나눈 나머지를 구한다. 가능한 부분 문자열 $t$는 총 $|s| - k + 1$개이다.
$f(t)$는 다음과 같이 정의된다.
어떤 줄에서 벌레 $i$의 $k$-문자열($k$-string)은 벌레 $i$부터 줄의 끝 방향으로 $k$마리의 벌레 길이를 이어붙인 문자열이다. 만약 $k$개보다 적은 벌레가 있다면 $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$개가 주어진다. 각 값은 $1$ 이상 $6$ 이하이다.
다음 $m$줄에는 수행할 연산이 한 줄에 하나씩 주어진다.
## 출력
입력된 3 s k 꼴의 연산의 결과를 한 줄에 하나씩 출력한다.
## 제한
$n \leq 200,000$, $m \leq 500,000$, $k \leq 50$
모든 $s$의 길이의 합: $\sum |s| \leq 10^7$
2 i 꼴의 연산의 총 횟수를 $c$라고 할 때, $c \leq 1000$
---
(뒷부분 생략)