#include "game.h"
#include<algorithm>
#include<vector>
int a,b,X,t;
long long seg[4096][4096];
long long gcd2(long long xx,long long yy){
if(yy==0)return xx;
return gcd2(yy,xx%yy);
}
long long yans(int xnum,int num,int s,int e,int px,int qx,int py,int qy)
{
if(s>qy||py>e)return (long long)0;
if(py<=s&&e<=qy)return seg[xnum][num];
return gcd2(yans(xnum,num*2,s,(s+e)/2,px,qx,py,qy),yans(xnum,num*2+1,(s+e)/2+1,e,px,qx,py,qy));
}
long long xans(int num,int s,int e,int px,int qx,int py,int qy)
{
if(s>qx||px>e)return (long long)0;
if(px<=s&&e<=qx)return yans(num,1,0,X-1,px,qx,py,qy);
return gcd2(xans(num*2,s,(s+e)/2,px,qx,py,qy),xans(num*2+1,(s+e)/2+1,e,px,qx,py,qy));
}
void init(int R, int C)
{
X=2048;
}
void update(int P, int Q, long long K)
{
int u=X+P,o;
o=X+Q;
seg[u][o]=K;o/=2;
while(o)
{
seg[u][o]=gcd2(seg[u][o*2],seg[u][o*2+1]);
o/=2;
}
u/=2;
while(u)
{
o=X+Q;
while(o)
{
seg[u][o]=gcd2(seg[u*2][o],seg[u*2+1][o]);
o/=2;
}
u/=2;
}
}
long long calculate (int P, int Q, int U, int V)
{
return xans(1,0,X-1,P,U,Q,V);
}
