暂无测试数据。

题目描述

将要读二年级的小 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 或 1 开头：

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

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

输出

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

样例输入

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

数据范围限制

测试数据分为A、B、C三类：
A类数据占 \(20\%\)，满足 \(N \leq 100\)，\(M \leq 100\)，\(T \leq 20000\)。
B类数据占 \(40\%\)，满足 \(N=1\)，\(M \leq 5 \times 10^5\)，\(T \leq 10^5\)。
C类数据占 \(40\%\)，满足 \(N*M \leq 5 \times 10^5\)，\(T \leq 10^5\)。
在每类数据中，均有 \(50\%\) 的数据满足每次修改操作仅含一个格子（即 \(x_1=x_2\),\(y_1=y_2\)）。
输入数据保证满足题目描述中的所有性质。

测试时限及内存限制

每个测试点时限：5秒
内存限制：512MB

来源

NOI2012