Comet OJ

C0382 [NOI2012Day1-C]魔幻棋盘

内存限制：512 MB 时间限制：5000 ms

题目描述

将要读二年级的小Q买了一款新型益智玩具——魔幻棋盘，它是一个𝑁行𝑀列的网格棋盘，每个格子中均有一个正整数。棋盘守护者在棋盘的第𝑋行第𝑌列（行与列均从1开始编号）并且始终不会移动。棋盘守护者会进行两种操作：

  • 询问：他会以自己所在位置为基础，向四周随机扩展出一块大小不定的矩形区域，向你询问这一区域内所有数的最大公约数是多少。
  • 修改：他会随意挑选棋盘上的一块矩形区域，将这一区域内的所有数同时加上一个给定的整数。

游戏说明书上附有这样一句话“聪明的小朋友，当你连续答对19930324次询问后会得到一个惊喜噢！”。小Q十分想得到这个惊喜，于是每天都在玩这个玩具。但由于他粗心大意，经常算错数，难以达到这个目标。于是他来向你寻求帮助，希望你帮他写一个程序来回答棋盘守护者的询问，并保证100%的正确率。

为了简化问题，你的程序只需要完成棋盘守护者的𝑇次操作，并且问题保证任何时刻棋盘上的数字均为不超过$2^{62}− 1$的正整数。

输入格式

第一行为两个正整数𝑁, 𝑀，表示棋盘的大小。
第二行为两个正整数𝑋, 𝑌，表示棋盘守护者的位置。
第三行仅有一个正整数𝑇，表示棋盘守护者将进行𝑇次操作。
接下来𝑁行，每行有𝑀个正整数，用来描述初始时棋盘上每个位置的数。
接下来𝑇行，按操作的时间顺序给出𝑇次操作。每行描述一次操作，以一个数字0或1开头：

若以数字0开头，表示此操作为询问，随后会有四个非负整数$𝑥_1, 𝑦_1, 𝑥_2, 𝑦_2$，表示询问的区域是以棋盘守护者的位置为基础向上扩展$𝑥_1$行，向下扩展$𝑥_2$行，向左扩展$𝑦_1$列，向右扩展$𝑦_2$列得到的矩形区域（详见样例）。

若以数字1开头，表示此操作为修改，随后会有四个正整数$𝑥_1, 𝑦_1, 𝑥_2, 𝑦_2$和一个整数$𝑐$，表示修改区域的上、下边界分别为第$𝑥_1, 𝑥_2$行，左、右边界分别为第$𝑦_1, 𝑦_2$列（详见样例），在此矩形区域内的所有数统一加上$𝑐$（注意𝑐可能为负数）。

输出

对于每次询问操作，每行输出一个数，表示该区域内所有数的最大公约数。

样例

样例输入 1

2 2
1 1
4
6 12
18 24
0 0 0 1 0
1 1 1 1 2 6
1 2 1 2 2 6
0 0 0 1 1

样例输出 1

6
6

提示

【样例说明】

屏幕快照 2019-06-05 下午8.06.52.png

对于第一、第四次操作（查询操作）后，加粗部分表示查询区域。
对于第二、第三次操作（修改操作）后，加粗部分表示修改区域。

【数据规模】

测试数据分为A、B、C三类：
A类数据占20%，满足$𝑁 ≤ 100，𝑀 ≤ 100，𝑇 ≤ 20000$。
B类数据占40%，满足$𝑁 = 1，𝑀 ≤ 500000，𝑇 ≤ 100000$。
C类数据占40%，满足$𝑁 ∗ 𝑀 ≤ 500000，𝑇 ≤ 100000$。在每类数据中，均有50%的数据满足每次修改操作仅含一个格子（即$𝑥_1=𝑥_2, 𝑦_1=𝑦_2$）。

输入数据保证满足题目描述中的所有性质。