P1219

[Noi2012]魔幻棋盘

[Noi2012]魔幻棋盘

给定一个 N×MN\times M 的棋盘，棋盘上的每个位置都有一个整数。棋盘守护者位于第 XX 行、第 YY 列。

你需要依次执行 TT 次操作。操作分为以下两种：

  • 询问操作：给定相对于棋盘守护者位置向上、向左、向下、向右扩展的距离，求所得矩形区域内所有数的最大公约数；
  • 修改操作：给定一个矩形区域和整数 cc，将该区域内的所有数统一加上 cc。

输入格式

第一行包含两个正整数 N,MN,M，表示棋盘的大小。

第二行包含两个正整数 X,YX,Y，表示棋盘守护者的位置。

第三行包含一个正整数 TT，表示操作次数。

接下来 NN 行，每行包含 MM 个正整数，描述棋盘上各位置的初始数值。

接下来 TT 行，按照时间顺序描述各次操作。每行以数字 00 或 11 开头：

  • 若开头为 00，则表示询问操作。随后输入四个非负整数 u,l,d,ru,l,d,r，询问区域为以棋盘守护者的位置为基准，向上扩展 uu 行、向左扩展 ll 列、向下扩展 dd 行、向右扩展 rr 列得到的矩形区域；
  • 若开头为 11，则表示修改操作。随后输入四个正整数 x1,y1,x2,y2x_1,y_1,x_2,y_2 和一个整数 cc，表示将第 x1x_1 行至第 x2x_2 行、第 y1y_1 列至第 y2y_2 列构成的矩形区域内的所有数统一加上 cc。其中，cc 可能为负数。

输出格式

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

样例输入

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

样例输出

6
6

数据范围

  • 1≤N,M≤5×1051\le N,M\le 5\times 10^5；
  • 1≤X≤N1\le X\le N，1≤Y≤M1\le Y\le M；
  • 1≤T≤1051\le T\le 10^5；
  • N×M≤5×105N\times M\le 5\times 10^5；
  • 对于询问操作，保证 0≤u<X0\le u<X、0≤l<Y0\le l<Y、0≤d≤N−X0\le d\le N-X、0≤r≤M−Y0\le r\le M-Y；
  • 对于修改操作，保证 1≤x1≤x2≤N1\le x_1\le x_2\le N、1≤y1≤y2≤M1\le y_1\le y_2\le M；
  • 初始棋盘上的数均为不超过 263−12^{63}-1 的正整数；
  • 修改量满足 ∣c∣≤263−1|c|\le 2^{63}-1；
  • 保证所有操作过程中涉及的棋盘数值、差分值及最大公约数的绝对值均不超过 263−12^{63}-1，即不会出现绝对值为 2632^{63} 的情况。

来源与许可

本题为 NOI 2012 试题「魔幻棋盘」，题面与测试数据整理自 BZOJ。

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

输出

6
6