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 翻译