Bazza and Shazza are playing a game. The board is a grid of cells, with $R$ rows number $0,\dots ,R-1$, and $C$ columns numbered $0,\dots ,C-1$. We let $(P,Q)$ denote the cell in row $P$ and column $Q$. Each cell contains a non-negative integer, and at the beginning of the game all of these integers are zero.

The game proceeds as follows. At any time, Bazza may either:

• update a cell $(P,Q)$, by assigning the integer that it contains;
• ask Shazza to calculate the greatest common divisor (GCD) of all integers within a rectangular block of cells, with opposite corners $(P,Q)$ and $(U,V)$ inclusive.

Bazza will take $N_U+N_Q$ actions (updating cells $N_U$ times and asking question $N_Q$ times) before he gets bored and goes outside to play cricket.

Your task is to work out the correct answers.

Example

Suppose $R=2$ and $C=3$, and Bazza begins with the following updates:

• Update cell $(0,0)$ to $20$;
• Update cell $(0,2)$ to $15$;
• Update cell $(1,1)$ to $12$.

The resulting grid is shown in the picture above. Bazza might then ask for GCDs in the following rectangles:

• Opposite corners $(0,0)$ and $(0,2)$: The three integers in this rectangle are $20$, $0$ and $15$, and their GCD is $5$.
• Opposite corners $(0,0)$ and $(1,1)$: The four integers in this rectangle are $20$, $0$, $0$, and $12$, and their GCD is $4$.

Now suppose Bazza makes the following updates:

• Update cell $(0,1)$ to $6$;
• Update cell $(1,1)$ to $14$.

The new grid is shown in the picture above. Bazza might then ask for GCDs in the following rectangles again:

• Opposite corners $(0,0)$ and $(0,2)$: Now the three integers in this rectangle are $20$, $6$ and $15$, and their GCD is $1$.
• Opposite corners $(0,0)$ and $(1,1)$: Now the four integers in this rectangle are $20$, $6$, $0$ and $14$, and their GCD is $2$.

Here Bazza has performed $N_U=5$ updates and $N_Q=4$ questions.

Procedures

You will first be given the initial size of the grid, allowing you to initialise any variables and data structures.

Parameters

• R: The number of rows.
• C: The number of columns.

Your Procedure: update()

Description

Your submission must implement this procedure.

This procedure will be called when Bazza assigns the number in some grid cell.

Parameters

• P: The row of the grid cell $(0\le P\le R-1)$
• Q: The column of the grid cell $(0\le Q\le C-1)$
• K: The new integer in this grid cell $(0\le K\le {10}^{18})$. May be the same as the current value.

Your Function: calculate()

Description

Your submission must implement this function.

This function should calculate the greatest common divisor of all integers in the rectangle with opposite corners $(P,Q)$ and $(U,V)$. This range is inclusive, i.e., the cells $(P,Q)$ and $(U,V)$ are included in the rectangle.

If all the integers in this rectangle are zero, then this function should return zero also.

Parameters

• P: The row of the top-left cell in the rectangle $(0\le P\le R-1)$
• Q: The column of the top-left cell in the rectangle $(0\le Q\le C-1)$
• U: The row of the bottom-right cell in the rectangle $(P\le U\le R-1)$.
• V: The column of the bottom-right cell in the rectangle $(Q\le V\le C-1)$
• Returns: The GCD of all integers in the rectangle, or $0$ if all those integers are zero.

Sample Session

The following session describes the example above:

Input Specification

The input will be in the following format:

• line $1$: $RCN$
• next $N$ lines: one action per line, in the order in which actions occur

The line for each action must be in one of the following formats:

• To indicate update: $1PQK$
• To indicate calculate: $2PQUV$

Output Specification

For every call of calculate, output an integer on a single line - the GCD of all integers in the calculated rectangle, or $0$ if all of those integers are zero.

Sample Input

2 3 9
1 0 0 20
1 0 2 15
1 1 1 12
2 0 0 0 2
2 0 0 1 1
1 0 1 6
1 1 1 14
2 0 0 0 2
2 0 0 1 1

Sample Output

5
4
1
2

Constraints

• $1\le R,C\le {10}^9$
• $0\le K\le {10}^{18}$, where $K$ is any integer that Bazza places in a grid cell.

Subtasks

Subtask	Points	$R$	$C$	$N_U$	$N_Q$
1	10	$\le 100$	$\le 100$	$\le 100$	$\le 100$
2	27	$\le 10$	$\le 100000$	$\le 10000$	$\le 250000$
3	26	$\le 2000$	$\le 2000$	$\le 10000$	$\le 250000$
4	17	$\le {10}^9$	$\le {10}^9$	$\le 10000$	$\le 250000$
5	20	$\le {10}^9$	$\le {10}^9$	$\le 22000$	$\le 250000$