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:

1. 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.
2. 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⁶² − 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₁, y₁, x₂, and y₂ will follow. This indicates that the query range of the chessboard guardian will span x₁ rows above him, x₂ rows below him, y₁ columns to his left, and y₂ 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₁, y₁, x₂, y₂ and an integer c will follow. This indicates that the upper and lower boundaries of the updated region are respectively x₁ and x₂, while the left and right boundaries of the region are respectively y₁ and y₂ (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

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₁ = x₂, y₁ = y₂).
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)