바자와 샤자

두 사람 바자(Bazza)와 샤자(Shazza)가 다음 게임을 하고 있다. 게임판은 셀로 이루어진 그리드로 되어 있고, R 개의 행이 차례로 번호가 0, …, R - 1 로 매겨져 있고 C 개의 열이 차례로 번호가 0, …, C - 1 로 매겨져 있다. (P, Q) 는 행 P , 열 Q 에 있는 셀을 나타낸다. 각 셀에는 음이 아닌 정수가 쓰여 있고, 게임이 시작될 때 모든 셀의 값은 0이다.

이 게임은 다음과 같이 진행된다. 게임 진행 중에, 바자는 다음 두 가지 중 하나를 할 수 있다.

• 셀 (P, Q) 의 값을 업데이트한다. 즉, 이 셀에 쓰여진 정수를 바꾼다.
• 샤자에게 주어진 직사각형 모양의 셀들 안의 모든 정수들의 (직사각형의 마주보는 양 모퉁이 (P, Q) , (U, V) 를 포함) 최대공약수(GCD)를 계산하도록 요청한다.

바자는 최대 NU + NQ 번 위와 같은 일을 (셀의 값을 NU 번 업데이트하고 NQ 번 질의을 함) 한 다음에는 지루해서 크리켓을 하러 간다.

당신의 임무는 정답을 구하는 것이다.

• 1 ≤ R, C ≤ 109
• 0 ≤ K ≤ 1018 . 여기서 K 는 바자가 그리드 셀에 써넣는 숫자이다.