Grid Game: GCD Queries

Bazza and Shazza are playing a game on a grid of size \(R \times C\). The rows are numbered from \(0\) to \(R-1\) and the columns from \(0\) to \(C-1\). We denote the cell at row \(p\) and column \(q\) as \((p, q)\). Initially, every cell contains the value \(0\).

Bazza performs \(N_U + N_Q\) operations. In each operation, he can do one of the following:

• Update Operation: Modify the integer in a cell \((p, q)\) to a specified non-negative integer \(x\). This is given in the input as:

1 p q x

• Query Operation: Ask Shazza to compute the greatest common divisor (GCD) of all the numbers within a submatrix whose two opposite corners are \((p, q)\) and \((u, v)\). This query is given as:

2 p q u v

Here, the submatrix includes both diagonal cells and all cells in between. Note that the values in cells that have not been updated remain \(0\), and you should use the standard definition of GCD where \(\gcd(0, a) = a\) and \(\gcd(0, 0) = 0\).

Your task is to process all the operations and for each query, output the correct GCD of the specified submatrix.

inputFormat

The first line contains three integers \(R\), \(C\), and \(M\), where \(M = N_U + N_Q\) is the total number of operations.

Each of the following \(M\) lines describes an operation. An operation is given in one of the following two formats:

• Update operation: 1 p q x — update the value at cell \((p, q)\) to \(x\).
• Query operation: 2 p q u v — query the GCD of all cells in the submatrix whose two opposite corners are \((p,q)\) and \((u,v)\).

All indices are 0-indexed.

outputFormat

For each query operation, output a line with a single integer representing the GCD of all numbers in the specified submatrix.

sample

3 3 4
1 0 0 12
1 1 1 18
2 0 0 1 1
2 0 0 2 2

6
6