IOI 2013 day2 3- 게임(Game) > 문제은행 : 정보올림피아드&알고리즘




2656 : 게임(Game)

제한시간
13000 ms   
메모리제한
230 MB   
해결횟수
7 회   
시도횟수
22 회   

문제

두 사람 바자(Bazza)와 샤자(Shazza)가 다음 게임을 하고 있다. 

게임판은 셀로 이루어진 그리드로 되어 있고, 

R 개의 행이 차례로 번호가 0, …, R - 1 로 매겨져 있고 C 개의 열이 차례로 번호가 0, …, C - 1 로 매겨져 있다. 

(P, Q) 는 행 P , 열 Q 에 있는 셀을 나타낸다. 

각 셀에는 음이 아닌 정수가 쓰여 있고, 게임이 시작될 때 모든 셀의 값은 0이다.

 

이 게임은 다음과 같이 진행된다. 게임 진행 중에, 바자는 다음 두 가지 중 하나를 할 수 있다.
• 셀 (P, Q) 의 값을 업데이트한다. 즉, 이 셀에 쓰여진 정수를 바꾼다.
• 샤자에게 주어진 직사각형 모양의 셀들 안의 모든 정수들의 

  (직사각형의 마주보는 양 모퉁이 (P, Q) , (U, V)를 포함) 최대공약수(GCD)를 계산하도록 요청한다.

 

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

 

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

 

예시
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로 업데이트

 

 

새로운 그리드는 위 그림과 같다. 그리고, 바자는 다음 직사각형에 대해서 다시 최대공약수 GCD를 질의한다.
• 양 모퉁이 (0, 0) , (0, 2) : 이 직사각형 안의 세 정수는 이제 20, 6, 15이고 최대공약수는 1이다.
• 양 모퉁이 (0, 0) , (1, 1) : 이 직사각형 안의 네 정수는 20, 6, 0, 14이고 최대공약수는 2이다.

 

여기까지 바자가 한 업데이트는 N = 5 회, 질의는 N = 4 회이다.


입력형식

입력의 첫 줄에 게임판의 행 크기 R (1≤R≤109)과 열 크기 C (1≤C≤109) 그리고 업데이트와 질의의 수 N (1≤N≤300000)이 공백으로 구분하여 들어온다.

다음 줄부터 N개의 줄이 들어오는데 각 줄은 다음 두 가지 형태중 하나의 형태로 들어온다. 

 

업데이트 : 1 P Q K 

질의     : 2 P Q U V

 

• P: 직사각형의 가장 왼쪽 위 셀의 행 번호 ( 0 ≤ P ≤ R - 1 ). 

• Q: 직사각형의 가장 왼쪽 위 셀의 열 번호 ( 0 ≤ Q ≤ C - 1 ). 

• K: 이 그리드 셀이 가지게 되는 새로운 값 ( 0 ≤ K ≤ 1018 ). 이전에 가졌던 값과 같을 수 있다. 

• U: 직사각형의 가장 오른쪽 아래 셀의 행 번호 ( P ≤ U ≤ R - 1 ). 

• V: 직사각형의 가장 오른쪽 아래 셀의 열 번호 ( Q ≤ V ≤ C - 1 ).

 

[Subtasks]


출력형식

각 질의에 대한 답 GCD를 각 줄에 출력한다. (단 모든 숫자들이 0인 경우에 GCD는 0이다.)


입력 예

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

출력 예

5
4
1
2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP