National Olympiad in Informatics, China, 2011
Just going into the second grade, little Q has purchased a popular educational game – the magic chessboard! This game takes place on an row by column grid, where each grid cell contains a single positive integer. The chessboard guardian is located at row , column (rows and columns are numbered starting from ) 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 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 a message reading "My smart young friends, when you have continuously answered 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 of the time.
To make this problem simpler, your program will only need to complete operations of the chessboard guardian. It is guaranteed that all numbers on the chessboard will be positive integers not exceeding .
Input Specification
The first line of input contains two positive integers and ,
representing the dimensions of the chessboard.
The second line contains two positive integers and , representing
the chessboard guardian's position.
The third line contains a positive integer , representing the number
of operations carried out by the chessboard guardian.
For the following lines, each line contains integers, describing
the numbers in all of the grid cells.
For the following lines, each line will describe a single operation.
Each line will start with either the number or :
- If the line starts with a , then this operation is a query. Four nonnegative integers , , , and will follow. This indicates that the query range of the chessboard guardian will span rows above him, rows below him, columns to his left, and columns to his right (refer to the sample below).
- If the line starts with a , then this operation is an update. Four positive integers , , , and an integer will follow. This indicates that the upper and lower boundaries of the updated region are respectively and , while the left and right boundaries of the region are respectively and (refer to the sample below). All of the numbers in this range are simultaneously incremented by (note that can be negative).
Output Specification
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
Sample Output
6
6
Explanation
Initial Status | After Operation 1 | After Operation 2 | After Operation 3 | After Operation 4 |
---|---|---|---|---|
6 12 18 24 |
6 12 18 24 |
12 18 18 24 |
12 18 24 30 |
12 18 24 30 |
After operations and (queries), the bold numbers represent the queried range. After operations and (updates), the bold numbers represent the updated range.
Constraints
There will be three types of test cases: , , and .
of cases are type , satisfying , , and .
of cases are type , satisfying , , and .
of cases are type , satisfying , and .
In each type, of test cases will have update operations only
concerning a single cell (i.e. ).
The input is guaranteed to satisfy all properties mentioned in the
description above.
Problem translated to English by .
Comments