AT_oupc2023_day1_q Kurukuru

本题中将使用以下数学符号记法： - $(i, j)$：表示 $2$ 维数组中自上而下第 $i + 1$ 行，自左而右第 $j + 1$ 列的位置。 - $A_{i, j}$：表示 $2$ 维数组 $A$ 的自上而下第 $i + 1$ 行，自左而右第 $j + 1$ 列的值。 - $p \bmod q$：表示用正整数 $q$ 去除非负整数 $p$ 所得的余数。 有一个 $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$ 个询问。每个询问输入 $6$ 个整数 $L, R, c, d, e, f$。对于 $A_{i,j} = i N + j$ 的 $N \times N$ 数组 $A$，依次执行第 $L$ 至第 $R$ 次操作，操作后得到的新数组 $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}$）有以下两种格式之一： > $1$ $x$ $y$ $a$ $b$ > $2$ 每个询问（$\mathrm{Query}$）格式如下： > $L$ $R$ $c$ $d$ $e$ $f$

输出共 $Q$ 行，第 $i$ 行为针对第 $i$ 个询问的答案。

## 小子任务 1.（$1$ 分）$N \leq 10$ 2.（$99$ 分）无其他限制 ## 样例解释 1 对于第 $1$ 个询问，从第 $2$ 到第 $3$ 个操作依次执行。操作前的二维数组为 $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 此测试用例不满足小子任务 $1$ 的约束条件。 ## 数据范围 - $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$ - 输入均为整数。 由 ChatGPT 5 翻译