問題文

この問題では以下の数式表現を用います。

• (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 で割った余りを求めてください。

制約

• 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
• 入力はすべて整数

小課題

1. (1 点) N\leq 10
2. (99 点) 追加の制約はない

入力例 1

3 5 2
1 1 1 2 1
1 2 1 0 2
2
1 1 2 1 0
2
2 3 0 1 1 2
1 5 0 2 0 2

出力例 1

24
36

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 の制約を満たします。

入力例 2

999999937 8 3
1 314159265 358979323 846264338 327950288
1 419716939 937510582 97494459 230781640
2
1 628620899 862803482 534211706 798214808
1 651328230 664709384 460955058 223172535
1 940812848 111745028 410270193 852110555
2
1 964462294 895493038 196442881 97566593
3 3 344612847 564823378 67831652 712019091
3 7 45648566 923460348 610454326 648213393
1 8 60726024 914127372 458700660 631558817

出力例 2

511746849
453803153
685820807

このテストケースは小課題 1 の制約を満たしません。