P5893 [IOI 2013] game 游戏

警告：**滥用本题评测将被封号**。

Bazza 和 Shazza 正在玩游戏。游戏在一个 $R$ 行 $C$ 列的网格上进行。其中， $R$ 行编号为 $0,\cdots, R - 1 $， $C$ 列编号为 $0,\cdots, C - 1 $。我们用 $(P, Q)$ 表示位于 $P$ 行 $Q$ 列的单元格。每个单元格包含一个非负整数，游戏开始时所有单元格内的整数均为零。 游戏如下进行：任意时刻，Bazza 可以做如下动作之一： - 修改一个单元格 $(p, q)$ 内包含的整数值； - 要求 Shazza 计算一个给定子矩阵中所有单元格内数字的最大公约数（GCD），子矩阵的两个对角分别为 $(p, q)$ 和 $(u, v)$ （子矩阵包含给定的两个对角点）。 Bazza 会做 $N_U + N_Q$ 次动作(其中，修改单元格内数据 $N_U$ 次，询问 GCD $N_Q$ 次) 。 你的任务是对 Bazza 提出的问题给出正确答案。

- 第1行: $R$ 表示网格行数，$C$ 表示网格列数，$N$ 表示操作总数。 - 接下来的 $N$ 行: 每行表示一个动作，以动作发生的先后顺序给出。 表示每个动作的一行的格式如下： - `update(P,Q,K)` 表示为： `1 P Q K` - `calculate(P,Q,U,V)` 表示为： `2 P Q U V`

共 $N_Q$ 行，对于每次询问，输出答案。 **说明** `update(P,Q,K)` - 当Bazza改变单元格中的整数时调用此函数，即把第 $P$ 行第 $Q$ 列的数改为 $K$。 - $P$: 单元格的行号（$0 \le P \le R - 1$ ）。 - $Q$: 单元格的列号（$0 \le Q \le C - 1$ ）。 - $K$: 这个单元格中新的整数（ $0 \le K \le 10^{18}$）。这个新整数可能与原来的整数相同。 `calculate(P,Q,U,V)` - 该函数计算以 $(P, Q)$ 和 $(U, V)$ 为对角点的子矩阵中所有整数的最大公约数。这个范围是包含单元格 $(P, Q)$ 和 $(U, V)$ 的。 - 如果这个子矩阵中的所有整数都是 $0$，那么该函数返回 $0$。 - $P$: 子矩阵左上角单元格的行号（ $0 \le P \le R - 1$ ）。 - $Q$: 子矩阵左上角单元格的列号 （$ 0 \le Q \le C - 1$ ）。 - $U$: 子矩阵右下角单元格的行号（ $P \le U \le R - 1$ ）。 - $V$: 子矩阵右下角单元格的列号（ $Q \le V \le C - 1$ ）。

**子任务** | 子任务 | 分数 | $R$ | $C$ | $N_U$ | $N_Q$ | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $\le 100$ | $\le 100$ | $\le 100$ | $\le 100$ | | $2$ | $27$ | $\le 10$ | $\le 10^5$ | $\le 10^4$ | $\le 2.5\times 10^5$ | | $3$ | $26$ | $\le 2 \times 10^3$ | $\le 2 \times 10^3$ | $\le 10^4$ | $\le 2.5 \times 10^5$ | | $4$ | $17$ | $\le 10^9$ | $\le 10^9$ | $\le 10^4$ | $\le 2.5 \times 10^5$ | | $5$ | $20$ | $\le 10^9$ | $\le 10^9$ | $\le 2.2 \times 10^4$ | $\le 2.5 \times 10^5$ | **限制** 对于 $100\%$ 的数据，$1 \le R,C \le 10^9$，$0 \le K \le 10^{18}$，$K$ 表示 Bazza 放到单元格中的数字。