#include "game.h"
//63point;
const int idx = 2048;
const int idx2 = 131072;
typedef long long ll;
int flag;
ll T[4100][4100];
ll T2[10][260000];
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;
else if(R<=10&&C<=100000)flag=2;
else flag=3;
}
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 update2(int x,int y,ll item)
{
y+=idx2;
T2[x][y]=item;
y>>=1;
while(y){
T2[x][y]=gc(T2[x][y<<1],T2[x][y<<1|1]);
y>>=1;
}
}
void update(int P, int Q, long long K){
if(flag==3)return;
if(flag==2)update2(P,Q,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;
}
ll read2(int t,int x,int y)
{
ll ret=0;
x+=idx2,y+=idx2;
while(x<=y){
ret=gc(ret,T2[t][x]);
ret=gc(ret,T2[t][y]);
x=(x+1)>>1;
y=(y-1)>>1;
}
return ret;
}
ll calculate2(int P, int Q, int U, int V){
ll ret=0;
for(int i=P;i<=U;i++)ret=gc(ret,read2(i,Q,V));
return ret;
}
ll calculate(int P, int Q, int U, int V){
if(flag==3)return -1;
if(flag==2)return calculate2(P,Q,U,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;
}
