Little Q, who is about to enter the second grade, bought a new type of puzzle toy—a Magic Chessboard. It is an $N \times M$ grid, where each cell contains a positive integer. The chessboard guardian is located at row $X$, column $Y$ (rows and columns are 1-indexed) and never moves. The guardian performs two types of operations:

(a) Query: Based on their own position, the guardian randomly expands a rectangular area of arbitrary size and asks you for the greatest common divisor (GCD) of all numbers within this area.

(b) Modify: The guardian randomly selects a rectangular area on the chessboard and adds a given integer to all numbers within this area.

The instruction manual contains the following sentence: "Clever child, if you answer 19,930,324 queries correctly in a row, you will receive a surprise!" Little Q really wants to get this surprise, so he plays with the toy every day. However, due to his carelessness, he often makes calculation errors and finds it difficult to reach this goal. Therefore, he comes to you for help, hoping you can write a program to answer the guardian's queries and ensure 100% accuracy.

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

Input

The first line contains two positive integers $N, M$, representing the size of the chessboard. The second line contains two positive integers $X, Y$, representing the position of the chessboard guardian. The third line contains a single positive integer $T$, representing the number of operations the guardian will perform. The next $N$ lines, each containing $M$ positive integers, describe the initial numbers in each cell of the chessboard. The next $T$ lines describe the $T$ operations in chronological order. Each line describes an operation, starting with a digit 0 or 1:

If it starts with 0, it is a query. It is followed by four non-negative integers $x_1, y_1, x_2, y_2$, representing the rectangular area obtained by extending $x_1$ rows up, $x_2$ rows down, $y_1$ columns left, and $y_2$ columns right from the guardian's position (see examples for details).

If it starts with 1, it is a modification. It is followed by four positive integers $x_1, x_2, y_1, y_2$ and an integer $c$, representing the modification area where the top and bottom boundaries are rows $x_1$ and $x_2$, and the left and right boundaries are columns $y_1$ and $y_2$ (see examples for details). All numbers in this rectangular area are increased by $c$ (note that $c$ can be negative).

Output

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

Examples

Input 1

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 1

6
6

Note

For the first and fourth operations (queries), the bold part represents the query area. For the second and third operations (modifications), the bold part represents the modification area.

Constraints

The test data is divided into three categories: A, B, and C: Category A accounts for 20%, satisfying $N \le 100, M \le 100, T \le 20000$. Category B accounts for 40%, satisfying $N = 1, M \le 500000, T \le 100000$. Category C accounts for 40%, satisfying $N \times M \le 500000, T \le 100000$. In each category, 50% of the data satisfies the condition that each modification operation involves 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 problem statement.