Super Sequence Scoring System

問題文

整数 $M$、長さ $N$ の整数列 $C=(C_1,C_2,\ldots,C_N)$、および $M \times M$ の整数行列 $W$ が与えられます。各 $C_i$ は $0$ 以上 $M-1$ 以下の整数です。

$Q$ 個のクエリが与えられるので、順に処理してください。

クエリは以下の $4$ 種類です。

• タイプ $1$：1 l r xの形式で与えられる。

  すべての整数 $i=l,l+1,\ldots,r$ について、$C_i$ を次の値に変更する。

  $C_i \leftarrow (C_i+x) \bmod M$

• タイプ $2$：2 l rの形式で与えられる。

  次の値を $998244353$ で割った余りを出力する。

  $\displaystyle \sum_{l \leq i < j \leq r} W_{C_i,C_j}$

• タイプ $3$：3 l r xの形式で与えられる。

  すべての整数 $i=l,l+1,\ldots,r$ について、$C_i$ を次の値に変更する。

  $C_i \leftarrow (C_i \times x) \bmod M$

• タイプ $4$：4 l r a bの形式で与えられる。

  区間 $[l,r]$ に含まれる値 $a$ と値 $b$ をすべて入れ替える。

  すなわち、次の操作を行う。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 10^4$
• $2 \leq M \leq 6$
• $0 \leq C_i < M$
• $0 \leq W_{i,j} < 998244353$
• 全てのタイプのクエリについて、$1 \leq l \leq r \leq N$
• タイプ $1$ のクエリについて、$0 \leq x < M$
• タイプ $3$ のクエリについて、$0 \leq x < M$
• タイプ $4$ のクエリについて、$0 \leq a < b < M$
• 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられます。

各クエリは、以下のいずれかの形式で与えられます。

出力

タイプ $2$ のクエリの個数を $q$ として、$q$ 行出力せよ。 $i$ 行目には $i$ 個目のタイプ $2$ のクエリに対する答えを出力せよ。

入力例１

4 3
0 1 2 0
0 1 2
3 4 5
6 7 8
6
2 1 2
1 2 4 1
3 1 3 2
4 1 4 0 1
2 1 4
2 2 3

出力例１

1
14
1

はじめ、数列は $C=(0,1,2,0)$ です。また、整数行列 $W$ は次のようになっています。

$1$ つ目のクエリでは、$C_1,C_2=(0,1)$ であり、答えは $W_{0,1}=1$ です。

$2$ つ目のクエリでは、区間 $[2,4]$ の各要素に $1$ を加え、$3$ で割った余りに置き換えます。よって、数列は $C=(0,2,0,1)$ となります。

$3$ つ目のクエリでは、区間 $[1,3]$ の各要素を $2$ 倍し、$3$ で割った余りに置き換えます。よって、数列は $C=(0,1,0,1)$ となります。

$4$ つ目のクエリでは、区間 $[1,4]$ に含まれる値 $0$ と値 $1$ を入れ替えます。よって、数列は $C=(1,0,1,0)$ となります。

$5$ つ目のクエリでは、答えは次のようになります。