### National Olympiad in Informatics, China, 2011

## Day 1, Problem 3 - Magic Chessboard

Just going into the second grade, little Q has purchased a popular educational game — the magic chessboard! This game takes place on an `N` row by `M` column grid, where each grid cell contains a single positive integer. The chessboard guardian is located at row `X`, column `Y` (rows and columns are numbered starting from 1) and will never move. The chessboard guardian will perform two types of operations:

- Query: Using his current location as a base, he will expand outwards in 4 directions to produce a rectangle of variable size. Then, you will be asked for the greatest common divisor of all integers in the region.
- Update: He will randomly choose a rectangular region on the chessboard and simultaneously add a fixed value to the integers on each of the cells in the region.

The game's instruction manual contains an message reading "My smart young friends, when you have continuously answered 19930324 correct queries, there will be a surprise!" Little Q is incredibly eager to discover the surprise, so he plays this game every day. However due to his carelessness, mistakes are very often made. So, he has come to you for help, hoping that you can write a program to help him correctly answer the chessboard guardian's queries 100% of the time.

To make this problem simpler, your program will only need to complete `T` operations of the chessboard guardian. It is guaranteed that all numbers on the chessboard will be positive integers not exceeding 2^{62} − 1.

### Input Format

The first line of input contains two positive integers `N` and `M`, representing the dimensions of the chessboard.

The second line contains two positive integers `X` and `Y`, representing the chessboard guardian's position.

The third line contains a positive integer `T`, representing the number of operations carried out by the chessboard guardian.

For the following `N` lines, each line contains `M` integers, describing the numbers in all of the grid cells.

For the following `T` lines, each line will describe a single operation. Each line will start with either the number 0 or 1:

- If the line starts with a 0, then this operation is a query. Four nonnegative integers
`x`_{1},`y`_{1},`x`_{2}, and`y`_{2}will follow. This indicates that the query range of the chessboard guardian will span`x`_{1}rows above him,`x`_{2}rows below him,`y`_{1}columns to his left, and`y`_{2}columns to his right (refer to the sample below). - If the line starts with a 1, then this operation is an update. Four positive integers
`x`_{1},`y`_{1},`x`_{2},`y`_{2}and an integer`c`will follow. This indicates that the upper and lower boundaries of the updated region are respectively`x`_{1}and`x`_{2}, while the left and right boundaries of the region are respectively`y`_{1}and`y`_{2}(refer to the sample below). All of the numbers in this range are simultaneously incremented by`c`(note that`c`can be negative).

### Output Format

For each query, output a single number on a separate line representing the greatest common divisor of the queried region.

### Sample Input

2 2 1 1 4 6 12 18 24 0 0 0 1 0 1 1 1 1 2 6 1 2 1 2 2 6 0 0 0 1 1

### Output Format

6 6

### Explanation

Initial Status | After Operation 1 | After Operation 2 | After Operation 3 | After Operation 4 |
---|---|---|---|---|

6 12 18 24 |
126 2418 |
121818 24 |
12 182430 |
12182430 |

After operations 1 and 4 (queries), the bold numbers represent the queried range. After operations 2 and 3 (updates), the bold numbers represent the updated range.

### Constraints

There will be three types of test cases: A, B, and C.

20% of cases are type A, satisfying `N` ≤ 100, `M` ≤ 100, and `T` ≤ 20000.

40% of cases are type B, satisfying `N` = 1, `M` ≤ 500000, and `T` ≤ 100000.

40% of cases are type C, satisfying `N` × `M` ≤ 500000, and `T` ≤ 100000.

In each type, 50% of test cases will have update operations only concerning a single cell (i.e. `x`_{1} = `x`_{2}, `y`_{1} = `y`_{2}).

The input is guaranteed to satisfy all properties mentioned in the description above.

All Submissions

Best Solutions

**Point Value:** 40 (partial)

**Time Limit:** 5.00s

**Memory Limit:** 512M

**Added:** Aug 13, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...