TopCoder

Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

69.4% (50/72)

Submission's AC Ratio

22.2% (183/826)

Tags

Description

巴勒與夏拉正在玩一個遊戲。遊戲盤是一個由R 列(以0, …, R – 1 標示)乘以C 行(以0, …,C – 1 標示)單元(cells)所構成的網格(grid)。我們以 (P, Q) 來表示位於第P 列、第Q 行的單元。每個單元包含一個非負整數,遊戲一開始時所有單元的值皆初始化為0。

遊戲進行的方式如下:在任何時間點,巴勒可以
 •更新(update)一個單元 (P, Q) 所包含的整數值。
 •要求夏拉計算一個矩形區域裡全部單元所包含數值的最大公因數(greatest common divisor,GCD),這個矩形透過給定其兩個對角 (P, Q) 與 (U, V) 來定義(對角單元包含在矩形內)。

巴勒在玩膩這個遊戲而跑到外面玩板球(cricket)前,最多將進行NU + NQ 個動作(更新NU次及要求計算NQ 次)。

你的任務是算出正確的答案。

Input Format

第一行有三個數字R C N,表示遊戲盤大小與巴勒的動作次數。

接下來 N 行,依照動作發生的順序,一個動作一行,表示動作的那一行必須是以下其中一種格式:

 •1 P Q K,表示更新(P,Q)的值為K。
 •2 P Q U V,表示查詢以(P, Q) 與 (U, V)為兩對角所構成的矩形內所有元素的最大公因數。

限制:
 •1 ≤ R, C ≤ 109
 •0 ≤ K ≤ 1018 ,K 是巴勒放置於網格單元的任何整數值。

Output Format

對於每個查詢,輸出一個數字表示答案,每個數字佔一行。

Sample Input 1

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 1

5
4
1
2

Hints

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。
此處巴勒總共進行了 NU = 5 次更新與NQ = 4 次要求計算。

Problem Source

IOI 2013

Subtasks

No. Testdata Range Score
1 0~10 10
2 11~17 27
3 18~26 26
4 27~37 17
5 38~47 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 235520 262144 1
1 1000 235520 262144 1
2 1000 235520 262144 1
3 1000 235520 262144 1
4 1000 235520 262144 1
5 1000 235520 262144 1
6 1000 235520 262144 1
7 1000 235520 262144 1
8 1000 235520 262144 1
9 1000 235520 262144 1
10 1000 235520 262144 1
11 3000 235520 262144 2
12 3000 235520 262144 2
13 3000 235520 262144 2
14 3000 235520 262144 2
15 3000 235520 262144 2
16 3000 235520 262144 2
17 3000 235520 262144 2
18 8000 235520 262144 3
19 8000 235520 262144 3
20 8000 235520 262144 3
21 8000 235520 262144 3
22 8000 235520 262144 3
23 8000 235520 262144 3
24 8000 235520 262144 3
25 8000 235520 262144 3
26 8000 235520 262144 3
27 10000 235520 262144 4
28 10000 235520 262144 4
29 10000 235520 262144 4
30 10000 235520 262144 4
31 10000 235520 262144 4
32 10000 235520 262144 4
33 10000 235520 262144 4
34 10000 235520 262144 4
35 10000 235520 262144 4
36 10000 235520 262144 4
37 10000 235520 262144 4
38 12000 235520 262144 5
39 12000 235520 262144 5
40 12000 235520 262144 5
41 12000 235520 262144 5
42 12000 235520 262144 5
43 12000 235520 262144 5
44 12000 235520 262144 5
45 12000 235520 262144 5
46 12000 235520 262144 5
47 12000 235520 262144 5