Bazza and Shazza are playing a game. The board is a grid of cells, with rows number , and columns numbered . We let denote the cell in row and column . Each cell contains a non-negative integer, and at the beginning of the game all of these integers are zero.
The game proceeds as follows. At any time, Bazza may either:
- update a cell , by assigning the integer that it contains;
- ask Shazza to calculate the greatest common divisor (GCD) of all integers within a rectangular block of cells, with opposite corners and inclusive.
Bazza will take actions (updating cells times and asking question times) before he gets bored and goes outside to play cricket.
Your task is to work out the correct answers.
Example
Suppose and , and Bazza begins with the following updates:
- Update cell to ;
- Update cell to ;
- Update cell to .
The resulting grid is shown in the picture above. Bazza might then ask for GCDs in the following rectangles:
- Opposite corners and : The three integers in this rectangle are , and , and their GCD is .
- Opposite corners and : The four integers in this rectangle are , , , and , and their GCD is .
Now suppose Bazza makes the following updates:
- Update cell to ;
- Update cell to .
The new grid is shown in the picture above. Bazza might then ask for GCDs in the following rectangles again:
- Opposite corners and : Now the three integers in this rectangle are , and , and their GCD is .
- Opposite corners and : Now the four integers in this rectangle are , , and , and their GCD is .
Here Bazza has preformed updates and questions.
Procedures
You will first be given the initial size of the grid, allowing you to initialise any variables and data structures.
Parameters
R
: The number of rows.C
: The number of columns.
Your Procedure: update()
Description
Your submission must implement this procedure.
This procedure will be called when Bazza assigns the number in some grid cell.
Parameters
P
: The row of the grid cellQ
: The column of the grid cellK
: The new integer in this grid cell . May be the same as the current value.
Your Function: calculate()
Description
Your submission must implement this function.
This function should calculate the greatest common divisor of all integers in the rectangle with opposite corners and . This range is inclusive, i.e., the cells and are included in the rectangle.
If all the integers in this rectangle are zero, then this function should return zero also.
Parameters
P
: The row of the top-left cell in the rectangleQ
: The column of the top-left cell in the rectangleU
: The row of the bottom-right cell in the rectangle .V
: The column of the bottom-right cell in the rectangle- Returns: The GCD of all integers in the rectangle, or if all those integers are zero.
Sample Session
The following session describes the example above:
Function Call | Returns |
---|---|
init(2, 3) | |
update(0, 0, 20) | |
update(0, 2, 15) | |
update(1, 1, 12) | |
calculate(0, 0, 0, 2) | 5 |
calculate(0, 0, 1, 1) | 4 |
update(0, 1, 6) | |
update(1, 1, 14) | |
calculate(0, 0, 0, 2) | 1 |
calculate(0, 0, 1, 1) | 2 |
Input Specification
The input will be in the following format:
- line :
- next lines: one action per line, in the order in which actions occur
The line for each action must be in one of the following formats:
- To indicate
update
: - To indicate
calculate
:
Output Specification
For every call of calculate, output an integer on a single line - the GCD of all integers in the calculated rectangle, or if all of those integers are zero.
Sample Input
2 3 9
1 0 0 20
1 0 2 15
1 1 1 12
2 0 0 0 2
2 0 0 1 1
1 0 1 6
1 1 1 14
2 0 0 0 2
2 0 0 1 1
Sample Output
5
4
1
2
Constraints
- , where is any integer that Bazza places in a grid cell.
Subtasks
Subtask | Points | ||||
---|---|---|---|---|---|
1 | 10 | ||||
2 | 27 | ||||
3 | 26 | ||||
4 | 17 | ||||
5 | 20 |
Comments