TopCoder

Thumb 100
johnchen902
我才不會讓你知道我有中二病的呢,哼!

User's AC Ratio

76.5% (39/51)

Submission's AC Ratio

22.2% (121/545)

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

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

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

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