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 $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 a 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\mathrm{\%}$ 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 Specification

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

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\mathrm{\%}$ of cases are type $A$, satisfying $N\le 100$, $M\le 100$, and $T\le 20000$.
$40\mathrm{\%}$ of cases are type $B$, satisfying $N=1$, $M\le 500000$, and $T\le 100000$.
$40\mathrm{\%}$ of cases are type $C$, satisfying $N\times M\le 500000$, and $T\le 100000$.
In each type, $50\mathrm{\%}$ 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.

Problem translated to English by Alex.