#include "game.h"
#include <bits/stdc++.h>
using namespace std;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
typedef long long ll;
int n,m;
struct nodex
{
int st,dr;
nodex *fiust,*fiudr;
long long val;
nodex(int stanga,int dreapta)
{
st=stanga;
dr=dreapta;
val=0;
fiust=fiudr=nullptr;
}
};
struct nodey
{
nodey(int stanga,int dreapta) : st(stanga), dr(dreapta), fiust(NULL), fiudr(NULL), fiux(1,m) {}
int st,dr;
nodex fiux;
nodey *fiust,*fiudr;
}*root;
ll query2(nodex *arb, int st,int dr)
{
if (arb == nullptr || arb->st>dr||st>arb->dr)
{
return 0;
}
if (st<=arb->st&&arb->dr<=dr)
{
return arb->val;
}
int mij=(arb->st+arb->dr)/2;
return gcd2(
query2(arb->fiust,st,dr),
query2(arb->fiudr,st,dr)
);
}
ll query1(nodey *arb ,int st,int dr,int p,int q,int u ,int v)
{
if (arb == NULL || st > u || dr<p)
{
return 0;
}
if (p<=st && dr<=u)
{
return query2(&arb->fiux,q,v);
}
int mij=(st+dr)/2;
return gcd2(
query1(arb->fiust,st,mij,p,q,u,v),
query1(arb->fiudr,mij+1,dr,p,q,u,v)
);
}
void init(int R, int C) {
n=R;
m=C;
root = new nodey(1,n);
}
void updatey(nodex *arb,int y,ll k)
{
int st = arb->st, dr = arb->dr, mij=(st+dr)/2;
if (st==dr)
{
arb->val=k;
return;
}
nodex **copil = &(y<=mij ? arb->fiust : arb->fiudr);
if (*copil == NULL)
{
*copil = new nodex (y,y);
(*copil)->val = k;
}
else
if ((*copil)->st<=y&&y<=(*copil)->dr)
{
updatey(*copil,y,k);
}
else
{
do
{
if (y<=mij)
{
dr=mij;
}
else
{
st=mij+1;
}
mij=(st+dr)/2;
}while ((y<=mij) == ((*copil)->dr<=mij));
nodex *nnode = new nodex(st,dr);
if ((*copil)->dr<=mij)
{
nnode->fiust = *copil;
}
else
{
nnode->fiudr = *copil;
}
*copil=nnode;
updatey(*copil,y,k);
}
arb->val = gcd2(
arb->fiust ? arb->fiust->val : 0 ,
arb->fiudr ? arb->fiudr->val : 0
);
}
void updatex(nodey *arb, int st,int dr,int x,int y,long long k)
{
int mij=(st+dr)/2;
if (st==dr)
{
updatey(&arb->fiux,y,k);
return;
}
if (x<=mij)
{
if (arb->fiust==NULL)
{
arb->fiust=new nodey(st,mij);
}
updatex(arb->fiust,st,mij,x,y,k);
}
else
{
if (arb->fiudr==NULL)
{
arb->fiudr= new nodey(mij+1,dr);
}
updatex(arb->fiudr,mij+1,dr,x,y,k);
}
ll val = gcd2(
arb->fiust ? query2(&arb->fiust->fiux,y,y) : 0,
arb->fiudr ? query2(&arb->fiudr->fiux,y,y) : 0
);
updatey(&arb->fiux,y,val);
}
void update(int P, int Q, long long K) {
P++;
Q++;
updatex(root,1,n,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
P++;Q++;U++;V++;
return query1(root ,1,n,P,Q,U,V);
}
#ifdef HOME
int main()
{
int n,m,q;
ifstream cin("date.in");
ofstream cout("date.out");
cin>>n>>m>>q;
init(n,m);
for (;q--;)
{
int tip;
cin>>tip;
if (tip==1)
{
long long x,y,val;
cin>>x>>y>>val;
update(x,y,val);
}
else
{
long long p,q,u,v;
cin>>p>>q>>u>>v;
cout<<calculate(p,q,u,v)<<'\n';
}
}
return 0;
}
#endif // HOME
