## IOI '13 P6 - Game (Standard I/O)

View as PDF

Points: 15 (partial)
Time limit: 8.0s
Memory limit: 512M

Problem types

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.

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

#### 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 cell
• Q: The column of the grid cell
• K: 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 rectangle
• Q: The column of the top-left cell in the rectangle
• U: 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.