Sequence Scoring System

この問題は $J$ 問題の部分問題です。 $J$ 問題を $AC$ したコードで正答することができます。

問題文

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

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

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

• タイプ $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}$

制約

• $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$ のクエリについて、$1 \leq l \leq r \leq N$
• タイプ $1$ のクエリについて、$0 \leq x < M$
• タイプ $2$ のクエリについて、$1 \leq l \leq r \leq N$
• 入力はすべて整数である

入力

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

出力

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

入力例１

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

出力例１

1
0
17

はじめ、数列 $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$つ目のクエリでは、区間 $[3,3]$ に含まれる要素は $1$ 個だけです。この区間からは、$i<j$ を満たす $2$ つの添字を選ぶことができません。したがって、答えは $0$ です。