#include "game.h"
//36point;
const int idx = 2048;
typedef long long ll;
bool flag;
ll T[4100][4100];
ll gc(ll x,ll y){
ll tmp=-1;
while(x!=tmp&&y)tmp=x,x=y,y=tmp%y;
return x;
}
void init(int R, int C){
if(R>2000||C>2000)flag=1;
}
void upd1(int x,int y,ll K)
{
int y1=y+idx;
T[x][y1]=gc(T[x<<1][y1],T[x<<1|1][y1]);
y1>>=1;
while(y1){
T[x][y1]=gc(T[x][y1<<1],T[x][y1<<1|1]);
y1>>=1;
}
}
void update(int P, int Q, long long K){
int p=P+idx,q=Q+idx;
T[p][q]=K;q>>=1;
while(q){T[p][q]=gc(T[p][q<<1],T[p][q<<1|1]);q>>=1;}
p>>=1;
while(p){
upd1(p,Q,K);
p>>=1;
}
}
ll cal1(int p,int s,int d)
{
int s1=s+idx,d1=d+idx;
ll ret=0;
while(s1<=d1){
ret=gc(ret,T[p][s1]);
ret=gc(ret,T[p][d1]);
s1=(s1+1)>>1;
d1=(d1-1)>>1;
}
return ret;
}
long long calculate(int P, int Q, int U, int V){
int p=P+idx,q=U+idx;
ll ret=0;
while(p<=q){
ret=gc(ret,cal1(p,Q,V));
ret=gc(ret,cal1(q,Q,V));
p=(p+1)>>1;
q=(q-1)>>1;
}
return ret;
}
