AT_oupc2023_day1_q Kurukuru

この問題では以下の数式表現を用います。 - $ (i,j) $ : $ 2 $ 次元配列の 上から $ i+1 $ 行目、左から $ j+1 $ 列目の場所 - $ A_{i,j} $ : $ 2 $ 次元配列 $ A $ の 上から $ i+1 $ 行目、左から $ j+1 $ 列目の値 - $ p \bmod q $ : 非負の整数 $ p $ を正の整数 $ q $ で割った余り $ N \times N $ の $ 2 $ 次元配列に対する $ M $ 個の操作が与えられます。各操作は整数 $ t $ といくつかの整数で表され、 $ t $ の値に応じて、 $ (i,j) $ ( $ 0 \leq i,j < N $ ) に対して以下の操作を同時に行います。 - $ t = 1 $ のとき、 $ (i, j) $ にある数値を $ ((i x + a) \bmod N, (j y + b) \bmod N) $ に移動させる。ただし $ x $ と $ N $ 、 $ y $ と $ N $ はどちらも互いに素であることが保証され、したがって各数値の移動先は重複しない。 - $ t = 2 $ のとき、 $ (i, j) $ にある数値を $ (j, i) $ に移動させる。 $ Q $ 個のクエリが与えられます。各クエリは $ L,R,c,d,e,f $ の $ 6 $ つの整数からなります。それぞれ $ A_{i,j} = i N + j $ である $ N \times N $ の $ 2 $ 次元配列 $ A $ に対して $ L, L + 1, \dots , R $ 番目の操作を順番に行い、操作後の $ 2 $ 次元配列 $ A' $ について $ \sum\limits_{i = c}^{d} \sum\limits_{j=e}^{f} A_{i, j}' $ を $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ M $ $ Q $ $ \mathrm{Operation}_1 $ $ \mathrm{Operation}_2 $ $ \vdots $ $ \mathrm{Operation}_M $ $ \mathrm{Query}_1 $ $ \mathrm{Query}_2 $ $ \vdots $ $ \mathrm{Query}_Q $ 各操作 ( $ \mathrm{Operation} $ ) は以下に示す $ 2 $ つの形式のいずれかです。 > $ 1 $ $ x $ $ y $ $ a $ $ b $ > $ 2 $ 各クエリ ( $ \mathrm{Query} $ ) は以下の形式です。 > $ L $ $ R $ $ c $ $ d $ $ e $ $ f $

$ Q $ 行出力してください。 $ i $ 行目には、 $ i $ 番目のクエリに対する答えを出力してください。

### 小課題 1. ( $ 1 $ 点) $ N\leq 10 $ 2. ( $ 99 $ 点) 追加の制約はない ### Sample Explanation 1 $ 1 $ 番目のクエリでは、 $ 2 $ 番目から $ 3 $ 番目までの操作を適用します。 操作前の $ 2 $ 次元配列は $ A=\begin{pmatrix} 0 & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \end{pmatrix} $ です。 $ 2 $ 番目の操作を適用すると、 $ \begin{pmatrix} 1 & 2 & 0 \\ 7 & 8 & 6 \\ 4 & 5 & 3 \end{pmatrix} $ となります。 さらに $ 3 $ 番目の操作を適用すると、 $ \begin{pmatrix} 1 & 7 & 4 \\ 2 & 8 & 5 \\ 0 & 6 & 3 \end{pmatrix} $ となります。 $ A' = \begin{pmatrix} 1 & 7 & 4 \\ 2 & 8 & 5 \\ 0 & 6 & 3 \end{pmatrix} $ としたとき、 $ \sum\limits_{i=0}^1 \sum\limits_{j=1}^2 A'_{i,j} = 7+4+8+5 = 24 $ です。 $ 2 $ 番目のクエリは、 $ 1 $ 番目から $ 5 $ 番目までの操作を適用します。すべての操作を適用した後、 $ A' = \begin{pmatrix} 5 & 3 & 4 \\ 8 & 6 & 7 \\ 2 & 0 & 1 \end{pmatrix} $ となりますが、当然そのすべての要素の和は操作前に等しく $ 36 $ です。 このテストケースは小課題 1 の制約を満たします。 ### Sample Explanation 2 このテストケースは小課題 1 の制約を満たしません。 ### Constraints - $ 2 \leq N \leq 10^{9} $ - $ 1 \leq M \leq 200{,}000 $ - $ 1 \leq Q \leq 200{,}000 $ - $ 1 \leq x < N $ - $ 1 \leq y < N $ - $ x $ と $ N $ , $ y $ と $ N $ は互いに素 - $ 0 \leq a < N $ - $ 0 \leq b < N $ - $ 1 \leq L \leq R \leq M $ - $ 0 \leq c \leq d < N $ - $ 0 \leq e \leq f < N $ - 入力はすべて整数