题目背景

警告：滥用本题评测将被封号。

题目描述

Bazza 和 Shazza 正在玩游戏。游戏在一个 $R$ 行 $C$ 列的网格上进行。其中， $R$ 行编号为 $0,\cdots, R - 1$， $C$ 列编号为 $0,\cdots, C - 1$。我们用 $(P, Q)$ 表示位于 $P$ 行 $Q$ 列的单元格。每个单元格包含一个非负整数，游戏开始时所有单元格内的整数均为零。

游戏如下进行：任意时刻，Bazza 可以做如下动作之一：

• 修改一个单元格 $(p, q)$ 内包含的整数值；
• 要求 Shazza 计算一个给定子矩阵中所有单元格内数字的最大公约数（GCD），子矩阵的两个对角分别为 $(p, q)$ 和 $(u, v)$ （子矩阵包含给定的两个对角点）。

Bazza 会做 $N_U + N_Q$ 次动作(其中，修改单元格内数据 $N_U$ 次，询问 GCD $N_Q$ 次) 。

你的任务是对 Bazza 提出的问题给出正确答案。

输入格式

• 第1行: $R$ 表示网格行数，$C$ 表示网格列数，$N$ 表示操作总数。
• 接下来的 $N$ 行: 每行表示一个动作，以动作发生的先后顺序给出。

表示每个动作的一行的格式如下：

• update(P,Q,K) 表示为： 1 P Q K
• calculate(P,Q,U,V) 表示为： 2 P Q U V

输出格式

共 $N_Q$ 行，对于每次询问，输出答案。

说明

update(P,Q,K)

• 当Bazza改变单元格中的整数时调用此函数，即把第 $P$ 行第 $Q$ 列的数改为 $K$。
• $P$: 单元格的行号（$0 \le P \le R - 1$ ）。
• $Q$: 单元格的列号（$0 \le Q \le C - 1$ ）。
• $K$: 这个单元格中新的整数（ $0 \le K \le 10^{18}$）。这个新整数可能与原来的整数相同。

calculate(P,Q,U,V)

• 该函数计算以 $(P, Q)$ 和 $(U, V)$ 为对角点的子矩阵中所有整数的最大公约数。这个范围是包含单元格 $(P, Q)$ 和 $(U, V)$ 的。

• 如果这个子矩阵中的所有整数都是 $0$，那么该函数返回 $0$。

• $P$: 子矩阵左上角单元格的行号（ $0 \le P \le R - 1$ ）。

• $Q$: 子矩阵左上角单元格的列号 （$0 \le Q \le C - 1$ ）。

• $U$: 子矩阵右下角单元格的行号（ $P \le U \le R - 1$ ）。

• $V$: 子矩阵右下角单元格的列号（ $Q \le V \le C - 1$ ）。

1 1 64
2 0 0 0 0
2 0 0 0 0
2 0 0 0 0
1 0 0 5352072091165800
2 0 0 0 0
1 0 0 15571253006461152
1 0 0 36204425277916896
1 0 0 80686018200191040
1 0 0 720602986354563312
2 0 0 0 0
1 0 0 90705271009665312
2 0 0 0 0
1 0 0 583803309300971760
1 0 0 3317329660750560
2 0 0 0 0
2 0 0 0 0
2 0 0 0 0
1 0 0 84776821924066272
1 0 0 581927323100969664
1 0 0 93139161501610224
1 0 0 28340661117472704
1 0 0 74529074218959360
2 0 0 0 0
1 0 0 462419028676725120
1 0 0 4416867915235776
1 0 0 840475934823549024
1 0 0 8247617084266560
1 0 0 117571055091706944
1 0 0 839204903894797440
1 0 0 820805176764813240
1 0 0 82688722861897152
1 0 0 136422472061715840
1 0 0 555837014267982720
1 0 0 935087613488388360
1 0 0 17770822018565616
1 0 0 10726679222715456
1 0 0 621229604181863040
1 0 0 12477973789689408
2 0 0 0 0
1 0 0 227153207069268480
1 0 0 262037449583477568
1 0 0 562837835495871936
1 0 0 131875056326325312
1 0 0 922430858108760
1 0 0 763487168205041280
2 0 0 0 0
2 0 0 0 0
1 0 0 551850903114166656
1 0 0 243713152409807808
1 0 0 306811355534716032
1 0 0 115604757169181280
2 0 0 0 0
1 0 0 29254579698314880
1 0 0 35080064244441216
1 0 0 97819409912384160
1 0 0 34259332503876480
2 0 0 0 0
2 0 0 0 0
1 0 0 159548730492191040
1 0 0 11555364984947784
2 0 0 0 0
1 0 0 3373083100427040
2 0 0 0 0
2 0 0 0 0

0
0
0
5352072091165800
720602986354563312
90705271009665312
3317329660750560
3317329660750560
3317329660750560
74529074218959360
12477973789689408
763487168205041280
763487168205041280
115604757169181280
34259332503876480
34259332503876480
11555364984947784
3373083100427040
3373083100427040

提示

子任务

限制

对于 $100\%$ 的数据，$1 \le R,C \le 10^9$，$0 \le K \le 10^{18}$，$K$ 表示 Bazza 放到单元格中的数字。