Background

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

Problem Description

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.

Input Format

• 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.

Output Format

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$).

1 1 64
2 0 0 0 0
2 0 0 0 0
2 0 0 0 0
1 0 0 5352072091165800
2 0 0 0 0
1 0 0 15571253006461152
1 0 0 36204425277916896
1 0 0 80686018200191040
1 0 0 720602986354563312
2 0 0 0 0
1 0 0 90705271009665312
2 0 0 0 0
1 0 0 583803309300971760
1 0 0 3317329660750560
2 0 0 0 0
2 0 0 0 0
2 0 0 0 0
1 0 0 84776821924066272
1 0 0 581927323100969664
1 0 0 93139161501610224
1 0 0 28340661117472704
1 0 0 74529074218959360
2 0 0 0 0
1 0 0 462419028676725120
1 0 0 4416867915235776
1 0 0 840475934823549024
1 0 0 8247617084266560
1 0 0 117571055091706944
1 0 0 839204903894797440
1 0 0 820805176764813240
1 0 0 82688722861897152
1 0 0 136422472061715840
1 0 0 555837014267982720
1 0 0 935087613488388360
1 0 0 17770822018565616
1 0 0 10726679222715456
1 0 0 621229604181863040
1 0 0 12477973789689408
2 0 0 0 0
1 0 0 227153207069268480
1 0 0 262037449583477568
1 0 0 562837835495871936
1 0 0 131875056326325312
1 0 0 922430858108760
1 0 0 763487168205041280
2 0 0 0 0
2 0 0 0 0
1 0 0 551850903114166656
1 0 0 243713152409807808
1 0 0 306811355534716032
1 0 0 115604757169181280
2 0 0 0 0
1 0 0 29254579698314880
1 0 0 35080064244441216
1 0 0 97819409912384160
1 0 0 34259332503876480
2 0 0 0 0
2 0 0 0 0
1 0 0 159548730492191040
1 0 0 11555364984947784
2 0 0 0 0
1 0 0 3373083100427040
2 0 0 0 0
2 0 0 0 0

0
0
0
5352072091165800
720602986354563312
90705271009665312
3317329660750560
3317329660750560
3317329660750560
74529074218959360
12477973789689408
763487168205041280
763487168205041280
115604757169181280
34259332503876480
34259332503876480
11555364984947784
3373083100427040
3373083100427040

Hint

Subtasks

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