先考虑只有一维的情况，要求支持区间加和求区间 (gcd)，根据 (gcd) 的性质，发现：
[ gcd(a_1,a_2,a_3,ldots a_n)=gcd(a_i,a_2-a_1,a_3-a_2,ldots a_n-a_{n-1})
]
其中 (a_i) 为原序列 (a) 中的任意一个元素，其与序列 (a) 的差分序列的 (gcd) 即为原序列的 (gcd)。根据该性质，对于一维的情况，就可以通过线段树单点修改维护差分序列，区间查询 (gcd) 来实现了。对于 (a_i)，根据修改维护其当前值即可。
然后考虑二维的情况，比如对于这样的一个 (4 imes 4) 的矩形：
[egin{aligned}
a_{1,1}quad a_{1,2}quad a_{1,3}quad a_{1,4} \
a_{2,1}quad a_{2,2}quad a_{2,3}quad a_{2,4} \
a_{3,1}quad a_{3,2}quad a_{3,3}quad a_{3,4} \
a_{4,1}quad a_{4,2}quad a_{4,3}quad a_{4,4}
end{aligned}
]
设棋盘守护者的位置为 ((x,y))，先对每一行进行差分，得：
[egin{aligned}
a_{1,y}quad a_{1,2}-a_{1,1}quad a_{1,3}-a_{1,2}quad a_{1,4}-a_{1,3} \
a_{2,y}quad a_{2,2}-a_{2,1}quad a_{2,3}-a_{2,2}quad a_{2,4}-a_{2,3} \
a_{3,y}quad a_{3,2}-a_{3,1}quad a_{3,3}-a_{3,2}quad a_{3,4}-a_{3,3} \
a_{4,y}quad a_{4,2}-a_{4,1}quad a_{4,3}-a_{4,2}quad a_{4,4}-a_{4,3}
end{aligned}
]
对每一行来维护差分序列，根据每一行的 (gcd)，就能求得整个矩形的 (gcd)。发现这样实现复杂度依然无法接受，于是对每一列也进行差分，也就是进行二维差分，得：
[egin{aligned}
&a_{x,y}qquadqquadqquadquad a_{x,2}-a_{x,1}qquadqquadqquadquad a_{x,3}-a_{x,2}qquadqquadqquadquad a_{x,4}-a_{x,3} \\
&a_{2,y}-a_{1,y}qquad a_{2,2}-a_{2,1}-a_{1,2}+a_{1,1}qquad a_{2,3}-a_{2,2}-a_{1,3}+a_{1,2}qquad a_{2,4}-a_{2,3}-a_{1,4}+a_{1,3} \\
&a_{3,y}-a_{2,y}qquad a_{3,2}-a_{3,1}-a_{2,2}+a_{2,1}qquad a_{3,3}-a_{3,2}-a_{2,3}+a_{2,2}qquad a_{3,4}-a_{3,3}-a_{2,4}+a_{2,3} \\
&a_{4,y}-a_{3,y}qquad a_{4,2}-a_{4,1}-a_{3,2}+a_{3,1}qquad a_{4,3}-a_{4,2}-a_{3,3}+a_{3,2}qquad a_{4,4}-a_{4,3}-a_{3,4}+a_{3,3}
end{aligned}
]
发现二维差分后的这个矩形的 (gcd) 即为原矩形的 (gcd)。然后考虑维护，对于第一行和第一列，去掉位置 ((1,1)) 的 (a_{x,y}) 后剩下的序列，其为一维上的问题，用两个一维线段树维护即可。对于去掉第一行和第一列的剩下的矩形，用二维线段树维护即可。两者都是只用支持单点修改和区间查询。对于 (a_{x,y})，根据修改维护其当前值即可。
二维线段树可以用树套树或者四分树来实现，因为树套树的空间不好处理，并且题目中也说明了查询是随机的，所以我这里用四分树来实现二维线段树了。
(code:)
#include<bits/stdc++.h>
#define maxn 2000010
#define maxm 32000010
#define a(i,j) a[(i-1)*m+j]
#define b(i,j) b[(i-1)*m+j]
#define ls (cur<<1)
#define rs (cur<<1|1)
#define mid ((l+r)>>1)
#define midx ((u+d)>>1)
#define midy ((l+r)>>1)
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,m,sx,sy,q,root,rt=1,tree_cnt;
int uls[maxm],urs[maxm],dls[maxm],drs[maxm];
ll w;
ll a[maxn],b[maxn],val[maxm];
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):abs(a);
}
void build(int u,int d,int l,int r,int &cur)
{
if(u>d||l>r) return;
if(!cur) cur=++tree_cnt;
if(u==d&&l==r)
{
val[cur]=b(u,l);
return;
}
build(u,midx,l,midy,uls[cur]),build(u,midx,midy+1,r,urs[cur]);
build(midx+1,d,l,midy,dls[cur]),build(midx+1,d,midy+1,r,drs[cur]);
val[cur]=gcd(gcd(val[uls[cur]],val[urs[cur]]),gcd(val[dls[cur]],val[drs[cur]]));
}
void modify(int u,int d,int l,int r,int x,int y,ll v,int cur)
{
if(l==r&&u==d)
{
val[cur]+=v;
return;
}
if(x<=midx)
{
if(y<=midy) modify(u,midx,l,midy,x,y,v,uls[cur]);
else modify(u,midx,mid+1,r,x,y,v,urs[cur]);
}
else
{
if(y<=midy) modify(midx+1,d,l,midy,x,y,v,dls[cur]);
else modify(midx+1,d,midy+1,r,x,y,v,drs[cur]);
}
val[cur]=gcd(gcd(val[uls[cur]],val[urs[cur]]),gcd(val[dls[cur]],val[drs[cur]]));
}
ll query(int U,int D,int L,int R,int u,int d,int l,int r,int cur)
{
if(U>D||L>R) return 0;
if(U<=u&&D>=d&&L<=l&&R>=r) return val[cur];
ll v=0;
if(U<=midx)
{
if(L<=midy) v=gcd(v,query(U,D,L,R,u,midx,l,midy,uls[cur]));
if(R>midy) v=gcd(v,query(U,D,L,R,u,midx,midy+1,r,urs[cur]));
}
if(D>midx)
{
if(L<=midy) v=gcd(v,query(U,D,L,R,midx+1,d,l,midy,dls[cur]));
if(R>midy) v=gcd(v,query(U,D,L,R,midx+1,d,midy+1,r,drs[cur]));
}
return v;
}
struct Segment_Tree
{
ll a[maxn],val[maxn];
void build(int l,int r,int cur)
{
if(l==r)
{
val[cur]=a[l];
return;
}
build(l,mid,ls),build(mid+1,r,rs);
val[cur]=gcd(val[ls],val[rs]);
}
void modify(int l,int r,int pos,ll v,int cur)
{
if(l==r)
{
val[cur]+=v;
return;
}
if(pos<=mid) modify(l,mid,pos,v,ls);
else modify(mid+1,r,pos,v,rs);
val[cur]=gcd(val[ls],val[rs]);
}
ll query(int L,int R,int l,int r,int cur)
{
if(L>R) return 0;
if(L<=l&&R>=r) return val[cur];
ll v=0;
if(L<=mid) v=gcd(v,query(L,R,l,mid,ls));
if(R>mid) v=gcd(v,query(L,R,mid+1,r,rs));
return v;
}
}T1,T2;
int main()
{
read(n),read(m),read(sx),read(sy),read(q);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
read(a(i,j));
for(int i=1;i<n;++i)
for(int j=1;j<m;++j)
b(i,j)=a(i+1,j+1)-a(i,j+1)-a(i+1,j)+a(i,j);
for(int i=1;i<n;++i) T1.a[i]=a(i+1,sy)-a(i,sy);
for(int i=1;i<m;++i) T2.a[i]=a(sx,i+1)-a(sx,i);
w=a(sx,sy),build(0,n,0,m,root),T1.build(0,n,root),T2.build(0,m,root);
while(q--)
{
int u,d,l,r,opt;
ll v;
read(opt),read(u),read(l),read(d),read(r);
if(!opt)
{
u=sx-u,l=sy-l,d=sx+d,r=sy+r;
v=gcd(w,query(u,d-1,l,r-1,0,n,0,m,root));
v=gcd(v,gcd(T1.query(u,d-1,0,n,rt),T2.query(l,r-1,0,m,rt)));
printf("%lld
",v);
}
else
{
read(v);
if(sx>=u&&sx<=d&&sy>=l&&sy<=r) w+=v;
if(sy>=l&&sy<=r) T1.modify(0,n,u-1,v,rt),T1.modify(0,n,d,-v,rt);
if(sx>=u&&sx<=d) T2.modify(0,m,l-1,v,rt),T2.modify(0,m,r,-v,rt);
modify(0,n,0,m,u-1,l-1,v,root),modify(0,n,0,m,d,r,v,root);
modify(0,n,0,m,u-1,r,-v,root),modify(0,n,0,m,d,l-1,-v,root);
}
}
return 0;
}