IOI '13  Brisbane, Australia
Game
Bazza and Shazza are playing a game. The board is a grid of cells, with R rows numbered 0, …, R  1, and C columns, numbered 0, …, C  1. We let (P, Q) denote the cell in row P and column Q. Each cell contains a nonnegative 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 (P, Q), 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 (P, Q) and (U, V) inclusive.
Bazza will take N_{U} + N_{Q} actions (updating cells N_{U} times and asking questions N_{Q} times) before he gets bored and goes outside to play cricket.
Your task is to work out the correct answers.
Example
Suppose R = 2 and C = 3, and Bazza begins with the following updates:
 Update cell (0, 0) to 20;
 Update cell (0, 2) to 15;
 Update cell (1, 1) to 12.
The resulting grid is shown in the picture above. Bazza might then ask for GCDs in the following rectangles:
 Opposite corners (0, 0) and (0, 2): The three integers in this rectangle are 20, 0 and 15, and their GCD is 5.
 Opposite corners (0, 0) and (1, 1): The four integers in this rectangle are 20, 0, 0 and 12, and their GCD is 4.
Now suppose Bazza makes the following updates:
 Update cell (0, 1) to 6;
 Update cell (1, 1) to 14.
The new grid is shown in the picture above. Bazza might then ask for GCDs in the following rectangles again:
 Opposite corners (0, 0) and (0, 2): Now the three integers in this rectangle are 20, 6 and 15, and their GCD is 1.
 Opposite corners (0, 0) and (1, 1): Now the four integers in this rectangle are 20, 6, 0 and 14, and their GCD is 2.
Here Bazza has performed N_{U} = 5 updates and N_{Q} = 4 questions.
Given the size of the grid, you should implement the operations update
and calculate
as described below.
To help you, below is a function gcd2(X, Y)
to compute the greatest common divisor of two nonnegative integers X and Y. If X = Y = 0 then gcd2(X, Y)
will return 0 also. This function is fast enough to score full points; in particular, the running time is at worst proportional to log(X + Y).
C/C++  Pascal 



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 (1 ≤ R ≤ 10^{9}).
 C: The number of columns (1 ≤ C ≤ 10^{9}).
update
: This operation will be called when Bazza assigns the number in some grid cell.
Parameters:
 P: The row of the grid cell (0 ≤ P ≤ R  1).
 Q: The column of the grid cell (0 ≤ Q ≤ C  1).
 K: The new integer in this grid cell (0 ≤ K ≤ 10^{18}). May be the same as the current value.
calculate
: This operation should calculate the greatest common divisor of all integers in the rectangle with opposite corners (P, Q) and (U, V). This range is inclusive, i.e., the cells (P, Q) and (U, V) are included in the rectangle.
If all integers in this rectangle are zero, then this function should return zero also.
Parameters:
 P: The row of the topleft cell in the rectangle (0 ≤ P ≤ R  1).
 Q: The column of the topleft cell in the rectangle (0 ≤ Q ≤ C  1).
 U: The row of the bottomright cell in the rectangle (0 ≤ U ≤ R  1).
 V: The column of the bottomright cell in the rectangle (0 ≤ V ≤ C  1).
 When this operation is called, you should output the GCD of all integers in the rectangle, or 0 if all of those integers are zero.
Input Format
The input will be in the following format:
 line 1:
R C N
 next N 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
:1 P Q K
 To indicate
calculate
:2 P Q U V
Output Format
For every call of calculate
, output an integer on a single line  the GCD of all integers in the calculated rectangle, or 0 if all of those integers are zero.
Sample Input and Description
The following case describes the example above.
Input  Description  Output 

2 3 9  R = 2, C = 3, N = 9 

1 0 0 20  update 0 0 20 

1 0 2 15  update 0 2 15 

1 1 1 12  update 1 1 12 

2 0 0 0 2  calculate 0 0 0 2  5 
2 0 0 1 1  calculate 0 0 1 1  4 
1 0 1 6  update 0 1 6 

1 1 1 14  update 1 1 4 

2 0 0 0 2  calculate 0 0 0 2  1 
2 0 0 1 1  calculate 0 0 1 1  2 
Subtasks
Subtask  Percent of Points  R  C  N_{U}  N_{Q} 

1  10  ≤ 100  ≤ 100  ≤ 100  ≤ 100 
2  27  ≤ 10  ≤ 100,000  ≤ 10,000  ≤ 250,000 
3  26  ≤ 2,000  ≤ 2,000  ≤ 10,000  ≤ 250,000 
4  17  ≤ 10^{9}  ≤ 10^{9}  ≤ 10,000  ≤ 250,000 
5  20  ≤ 10^{9}  ≤ 10^{9}  ≤ 22,000  ≤ 250,000 
All Submissions
Best Solutions
Point Value: 30 (partial)
Time Limit: 16.00s
Memory Limit: 512M
Added: Jul 28, 2013
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
I keep getting SIGABRT, am I using too much memory or is it something else?
If you're not throwing an exception, the STL must be.
If you're not using checked vector access, then the exception is probably bad_alloc.
If you can't figure this out yourself, well...
On test 3d i'm getting RE,however on my computer i get AC on first 5 tests of subtask 2,what's happening?
This information is listed in the README.