바자와 샤자

두 사람 바자(Bazza)와 샤자(Shazza)가 다음과 같은 게임을 한다. 게임판은 $R$개의 행과 $C$개의 열로 이루어진 격자이다. 행에는 위에서부터 $0, 1, \dots, R-1$의 번호가, 열에는 왼쪽부터 $0, 1, \dots, C-1$의 번호가 매겨져 있다. $(P, Q)$는 행 $P$, 열 $Q$에 있는 칸을 뜻한다. 각 칸에는 음이 아닌 정수가 하나씩 적혀 있으며, 게임을 시작할 때 모든 칸의 값은 $0$이다.

게임이 진행되는 동안 바자는 다음 두 가지 작업 중 하나를 할 수 있다.

• 갱신: 칸 $(P, Q)$에 적힌 정수를 새로운 값으로 바꾼다.
• 질의: 두 꼭짓점 $(P, Q)$와 $(U, V)$를 마주 보는 모퉁이로 하는 직사각형(테두리 포함) 안에 있는 모든 정수의 최대공약수(GCD)를 계산한다.

바자는 이 작업을 최대 $N_U + N_Q$번(값을 $N_U$번 갱신하고 $N_Q$번 질의) 수행한 뒤 게임을 그만둔다. 각 질의에 대한 최대공약수를 순서대로 구하는 것이 목표이다.

예를 들어 $R = 2$, $C = 3$이고 바자가 다음 순서로 값을 갱신했다고 하자.

• 칸 $(0, 0)$을 $20$으로 갱신
• 칸 $(0, 2)$를 $15$로 갱신
• 칸 $(1, 1)$을 $12$로 갱신

이때 격자는 위 그림과 같다. 이어서 바자가 다음 두 직사각형의 최대공약수를 질의한다.

• 모퉁이 $(0, 0)$, $(0, 2)$: 직사각형 안의 세 정수는 $20, 0, 15$이고 최대공약수는 $5$이다.
• 모퉁이 $(0, 0)$, $(1, 1)$: 직사각형 안의 네 정수는 $20, 0, 0, 12$이고 최대공약수는 $4$이다.

다시 바자가 다음과 같이 값을 갱신한다.

• 칸 $(0, 1)$을 $6$으로 갱신
• 칸 $(1, 1)$을 $14$로 갱신

바뀐 격자는 위 그림과 같다. 바자가 같은 두 직사각형을 다시 질의한다.

• 모퉁이 $(0, 0)$, $(0, 2)$: 세 정수는 $20, 6, 15$이고 최대공약수는 $1$이다.
• 모퉁이 $(0, 0)$, $(1, 1)$: 네 정수는 $20, 6, 0, 14$이고 최대공약수는 $2$이다.

여기까지 바자는 값을 $N_U = 5$번 갱신하고 $N_Q = 4$번 질의했다.

첫째 줄에 행의 개수 $R$, 열의 개수 $C$, 작업의 개수 $N$이 공백으로 구분되어 주어진다. ($1 \le R, C \le 10^9$)

다음 $N$개의 줄에는 작업이 일어난 순서대로 한 줄에 하나씩 주어진다. 갱신 작업은 최대 $N_U \le 22{,}000$번, 질의 작업은 최대 $N_Q \le 250{,}000$번 주어진다.

• 갱신 작업은 1 P Q K 꼴이며, 칸 $(P, Q)$의 값을 $K$로 바꾼다. ($0 \le P \le R-1$, $0 \le Q \le C-1$, $0 \le K \le 10^{18}$)
• 질의 작업은 2 P Q U V 꼴이며, 두 꼭짓점 $(P, Q)$와 $(U, V)$를 모퉁이로 하는 직사각형(테두리 포함) 안에 있는 모든 값의 최대공약수를 구한다. ($0 \le P \le U \le R-1$, $0 \le Q \le V \le C-1$)

직사각형 안의 모든 값이 $0$이면 최대공약수는 $0$으로 정의한다.

질의 작업이 주어질 때마다, 해당 직사각형 안에 있는 모든 값의 최대공약수를 한 줄에 하나씩 순서대로 출력한다.