P5893 [IOI 2013] game

Warning: **Abusing the judge for this problem will result in your account being banned**.

Bazza and Shazza are playing a game. The game is played on a grid with $R$ rows and $C$ columns. The $R$ rows are numbered $0,\cdots, R - 1$, and the $C$ columns are numbered $0,\cdots, C - 1$. We use $(P, Q)$ to denote the cell located in row $P$ and column $Q$. Each cell contains a non-negative integer, and at the start of the game, all integers in all cells are zero. The game proceeds as follows: at any time, Bazza can perform one of the following actions: - Modify the integer value contained in a cell $(p, q)$. - Ask Shazza to compute the greatest common divisor (GCD) of all numbers in a given submatrix, whose two opposite corners are $(p, q)$ and $(u, v)$ (the submatrix includes these two corner cells). Bazza will perform a total of $N_U + N_Q$ actions (including $N_U$ cell updates and $N_Q$ GCD queries). Your task is to output the correct answer for each question asked by Bazza.

- Line 1: $R$ is the number of rows in the grid, $C$ is the number of columns in the grid, and $N$ is the total number of operations. - The next $N$ lines: each line describes an action, given in the order they occur. The format of each action line is: - `update(P,Q,K)` is given as: `1 P Q K`. - `calculate(P,Q,U,V)` is given as: `2 P Q U V`.

There are $N_Q$ lines. For each query, output the answer. **Notes** `update(P,Q,K)` - This function is called when Bazza changes the integer in a cell, i.e. set the number in row $P$, column $Q$ to $K$. - $P$: the row index of the cell ($0 \le P \le R - 1$). - $Q$: the column index of the cell ($0 \le Q \le C - 1$). - $K$: the new integer in this cell ($0 \le K \le 10^{18}$). This new integer may be the same as the previous one. `calculate(P,Q,U,V)` - This function computes the GCD of all integers in the submatrix with corners $(P, Q)$ and $(U, V)$. This range includes the cells $(P, Q)$ and $(U, V)$. - If all integers in this submatrix are $0$, then this function returns $0$. - $P$: the row index of the top-left cell of the submatrix ($0 \le P \le R - 1$). - $Q$: the column index of the top-left cell of the submatrix ($0 \le Q \le C - 1$). - $U$: the row index of the bottom-right cell of the submatrix ($P \le U \le R - 1$). - $V$: the column index of the bottom-right cell of the submatrix ($Q \le V \le C - 1$).

**Subtasks** | Subtask | Score | $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$ | **Constraints** For $100\%$ of the testdata, $1 \le R,C \le 10^9$, $0 \le K \le 10^{18}$, where $K$ is the number Bazza puts into a cell. Translated by ChatGPT 5