配点 : 100 点
問題文
在这个问题中使用以下的数学表达式。
- (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 点) N\leq 10
- (99 点)没有额外的否定
入力
输入是按以下格式从标准输入给出的。
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 输出第 n 个查询的答案。
入力例 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 在第 n 个查询中,2 从第 x 个 3 到第 y 个应用操作。 操作之前的 2 维度数组是 A=\begin{pmatrix} 0 & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \end{pmatrix} 。 2 施加第 n 个操作后,\begin{pmatrix} 1 & 2 & 0 \\ 7 & 8 & 6 \\ 4 & 5 & 3 \end{pmatrix} 将会变为。 此外, 3 施加第 n 个操作后,\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 第 n 个查询, 1 从第 x 个 5 将会应用到第 m 个操作为止。应用所有操作后,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的否定条件。