#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int MAX=2010;
long long gcd(long long a, long long b)
{
if(b==0)return a;
return gcd(b,a%b);
}
long long n,m;
long long tree[4*MAX][4*MAX];
long long tree2[4*MAX][4*MAX];
void init(int R, int C)
{
n=R,m=C;
}
long long sumy(long long nodex, long long nodey, long long L, long long R, long long _left, long long _right)
{
if(m<=2000)
{
if(L>=_left && R<=_right)return tree[nodex][nodey];
else if(L>_right || R<_left)return 0;
long long mid=(L+R)/2;
long long l=sumy(nodex,2*nodey,L,mid,_left,_right);
long long r=sumy(nodex,2*nodey+1,mid+1,R,_left,_right);
return gcd(l,r);
}
else
{
if(L>=_left && R<=_right)return tree2[nodex][nodey];
else if(L>_right || R<_left)return 0;
long long mid=(L+R)/2;
long long l=sumy(nodex,2*nodey,L,mid,_left,_right);
long long r=sumy(nodex,2*nodey+1,mid+1,R,_left,_right);
return gcd(l,r);
}
}
long long sumx(long long node, long long L, long long R, long long _leftx, long long _rightx, long long _lefty, long long _righty)
{
if(L>=_leftx && R<=_rightx)
{
return sumy(node,1,0,m-1,_lefty,_righty);
}
else if(L>_rightx || R<_leftx)return 0;
long long mid=(L+R)/2;
long long l=sumx(2*node,L,mid,_leftx,_rightx,_lefty,_righty);
long long r=sumx(2*node+1,mid+1,R,_leftx,_rightx,_lefty,_righty);
return gcd(l,r);
}
void updatey(long long nodex, long long Lx, long long Rx, long long nodey, long long Ly, long long Ry, long long row, long long col, long long val)
{
if(m<=2000)
{
if(Ly==Ry)
{
if(Lx==Rx)
{
tree[nodex][nodey]=val;
}
else
{
tree[nodex][nodey]=gcd(tree[2*nodex][nodey],tree[2*nodex+1][nodey]);
}
}
else
{
long long mid=(Ly+Ry)/2;
if(col>mid)updatey(nodex,Lx,Rx,2*nodey+1,mid+1,Ry,row,col,val);
else updatey(nodex,Lx,Rx,2*nodey,Ly,mid,row,col,val);
tree[nodex][nodey]=gcd(tree[nodex][2*nodey],tree[nodex][2*nodey+1]);
}
}
else
{
if(Ly==Ry)
{
if(Lx==Rx)
{
tree2[nodex][nodey]=val;
}
else
{
tree2[nodex][nodey]=gcd(tree2[2*nodex][nodey],tree2[2*nodex+1][nodey]);
}
}
else
{
long long mid=(Ly+Ry)/2;
if(col>mid)updatey(nodex,Lx,Rx,2*nodey+1,mid+1,Ry,row,col,val);
else updatey(nodex,Lx,Rx,2*nodey,Ly,mid,row,col,val);
tree2[nodex][nodey]=gcd(tree2[nodex][2*nodey],tree2[nodex][2*nodey+1]);
}
}
}
void updatex(long long node, long long L, long long R, long long row, long long col, long long val)
{
if(L!=R)
{
long long mid=(L+R)/2;
if(row>mid)updatex(2*node+1,mid+1,R,row,col,val);
else updatex(2*node,L,mid,row,col,val);
}
updatey(node,L,R,1,0,m-1,row,col,val);
}
long long calculate(int P, int Q, int U, int V)
{
return sumx(1,0,n-1,P,U,Q,V);
}
void update(int P, int Q, long long K)
{
updatex(1,0,n-1,P,Q,K);
}
