魔幻棋盘

魔幻棋盘

测试数据来自 system/1806

描述

将要读二年级的小Q买了一款新型益智玩具——魔幻棋盘,它是一个 N 行 M 列的网格棋盘,每个格子中均有一个正整数。棋盘守护者在棋盘的第 X 行第 Y 列(行与列均从 1 开始编号)并且始终不会移动。棋盘守护者会进行两种操作:
(a)询问:他会以自己所在位置为基础,向四周随机扩展出一块大小不定的矩形区域,向你询问这一区域内所有数的最大公约数是多少。
(b)修改:他会随意挑选棋盘上的一块矩形区域,将这一区域内的所有数同时加上一个给定的整数。
游戏说明书上附有这样一句话“聪明的小朋友,当你连续答对 19930324 次询问后会得到一个惊喜噢!”。小Q十分想得到这个惊喜,于是每天都在玩这个玩具。但由于他粗心大意,经常算错数,难以达到这个目标。于是他来向你寻求帮助,希望你帮他写一个程序来回答棋盘守护者的询问,并保证 100% 的正确率。
为了简化问题,你的程序只需要完成棋盘守护者的T次操作,并且问题保证任何时刻棋盘上的数字均为不超 过2^62 − 1 的正整数。

格式

输入格式

第一行为两个正整数 N、M,表示棋盘的大小。
第二行为两个正整数 X、Y,表示棋盘守护者的位置。
第三行仅有一个正整数 T ,表示棋盘守护者将进行T 次操作。
接下来 N 行,每行有 M 个正整数,用来描述初始时棋盘上每个位置的数。
接下来 T 行,按操作的时间顺序给出T 次操作。每行描述一次操作,以一若以数字 0 开头,表示此操作为询问,随后会有四个非负整数x1,y1,x2,y2,表示询问的区域是以棋盘守护者的位置为基础向上扩展 x1 行,向下扩展 x2行,向左扩展 y1 列,向右扩展 y2列得到的矩形区域(详见样例)。
若以数字1 开头,表示此操作为修改,随后会有四个正整数x1,y1,x2,y2 和一个整数c,表示修改区域的上、下边界分别为第x1, x2 行,左、右边界分别为第y1, y2 列(详见样例),在此矩形区域内的所有数统一加上c(注意c可能为负数)。

输出格式

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

样例1

样例输入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

限制

测试数据分为A、B、C 三类:
A 类数据占20%,满足N ≤ 100,M ≤ 100,T ≤ 20000。
B 类数据占40%,满足N = 1,M ≤ 500000,T ≤ 100000。
C 类数据占40%,满足N ∗ M ≤ 500000,T ≤ 100000。
在每类数据中,均有50% 的数据满足每次修改操作仅含一个格子(即x1 = x2, y1 = y2)。
输入数据保证满足题目描述中的所有性质。
每个测试点5s。

来源

NOI 2012 Day 1 P3

信息

ID
1839
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者