바자와 샤자

시간 제한13초메모리 제한230 MB

요약

셀이 모두 0인 거대한 격자에서 한 칸 값을 바꾸는 갱신과 직사각형 영역의 최대공약수를 구하는 질의를 처리한다. 좌표는 10^9, 값은 10^18까지다.

난이도: 어려움10점 중 8점
유형: 세그먼트 트리, 동적 계획법, 수학, 정수론
정답자: 아직 제출이 없습니다

문제

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

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

셀 (P, Q)의 값을 업데이트한다. 즉, 이 셀에 쓰여진 정수를 바꾼다.
샤자에게 주어진 직사각형 모양의 셀들 안의 모든 정수의 최대공약수(GCD)를 계산해 달라고 요청한다. 이때 직사각형은 서로 마주보는 두 모퉁이 (P, Q)와 (U, V)로 주어지며, 두 모퉁이도 포함한다.

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

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

제한

1 ≤ R, C ≤ 10^9
0 ≤ K ≤ 10^18. 여기서 K는 바자가 그리드 셀에 써넣는 숫자이다.

예제1

예제 1
입력
```
1 1
2
1 0 0 7
2 0 0 0 0
```
예상 출력
```
7
```