Description

Little Q, who is about to enter second grade, bought a new type of puzzle toy — the Magic Chessboard. It is a grid board with $N$ rows and $M$ columns, and each cell contains a positive integer. The board guardian stands at the $X$-th row and the $Y$-th column (rows and columns are numbered starting from $1$) and will never move. The board guardian performs two types of operations:

• (a) Query: Based on his position, he expands in the four directions to form a rectangle of arbitrary size and asks you for the greatest common divisor of all numbers in this region.
• (b) Modify: He arbitrarily selects a rectangular region on the board and adds a given integer to all numbers in this region.

The game manual includes this sentence: “Smart kids, when you answer $19930324$ consecutive queries correctly, you will get a surprise!” Little Q really wants this surprise, so he plays this toy every day. However, because he is careless, he often makes mistakes and cannot reach this goal. He now seeks your help, hoping you can write a program to answer the guardian’s queries with $100\%$ accuracy.

To simplify the problem, your program only needs to process $T$ operations from the board guardian, and it is guaranteed that at any time all numbers on the board are positive integers not exceeding $2^{62} - 1$.

Input Format

The first line contains two positive integers $N, M$, representing the size of the board.

The second line contains two positive integers $X, Y$, representing the position of the board guardian.

The third line contains a single positive integer $T$, representing that the board guardian will perform $T$ operations.

The next $N$ lines each contain $M$ positive integers, describing the initial numbers at each position on the board.

The next $T$ lines, in chronological order, describe the $T$ operations. Each line starts with a digit $0$ or $1$:

• If it starts with $0$, the operation is a query, followed by four non-negative integers $x_1, y_1, x_2, y_2$. The queried rectangle is obtained by expanding, based on the guardian’s position, $x_1$ rows upward, $x_2$ rows downward, $y_1$ columns to the left, and $y_2$ columns to the right (see the sample).
• If it starts with $1$, the operation is a modification, followed by four positive integers $x_1, y_1, x_2, y_2$ and an integer $c$. The upper and lower boundaries of the modified region are rows $x_1$ and $x_2$, and the left and right boundaries are columns $y_1$ and $y_2$ (see the sample). All numbers in this rectangle are increased by $c$ (note that $c$ may be negative).

Output Format

For each query operation, output one number per line, which is the greatest common divisor of all numbers in the specified region.

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

6
6

Hint

After the first and fourth operations (queries), the boldfaced part indicates the query region.

After the second and third operations (modifications), the boldfaced part indicates the modification region.

The testdata is divided into three categories A, B, and C:

• Category A accounts for $20\%$, satisfying $N \leq 100$, $M \leq 100$, $T \leq 2\times 10^4$.
• Category B accounts for $40\%$, satisfying $N = 1$, $M \leq 5\times 10^5$, $T \leq 10^5$.
• Category C accounts for $40\%$, satisfying $N \times M \leq 5\times 10^5$, $T \leq 10^5$.

In each category, $50\%$ of the testdata satisfies that each modification affects only one cell (i.e., $x_1 = x_2$, $y_1 = y_2$).

The input data is guaranteed to satisfy all properties described in the statement.

Translated by ChatGPT 5