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 performed updates and questions.
Implementation
You should submit a file implementing the procedures init()
and update()
and the function calculate()
, and described below.
Your procedure: init()
C/C++
void init(int R, int C);
Pascal
procedure init(R, C : LongInt);
Description
Your submission must implement this procedure.
This procedure give you the initial size of the grid, and allows you to initialise any global variables and data structures. It will only be called once, before any calls to
update()
orcalculate()
.
Parameters
R
: The number of rows.C
: The number of columns.
Your Procedure: update()
C/C++
void update(int P, int Q, long long K);
Pascal
procedure update(P, Q : LongInt; K : Int64);
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()
C/C++
long long calculate(int P, int Q, int U, int V);
Pascal
function calculate(P, Q, U, V : LongInt) : Int64;
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 |
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