#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int R,C,Q;
struct node1d
{
ll val=0;
int pos = -1;
node1d *lc=nullptr,*rc=nullptr;
void update(int s,int e,int t,ll v)
{
if(e<t || t<s )
return ;
if(s==e)
{
val=v;
return;
}
int m = (s+e)/2;
if(pos>=0)
{
if(pos<=m)
{
lc = new node1d;
lc->pos=pos,lc->val=val;
}
else
{
rc = new node1d;
rc->pos=pos,rc->val=val;
}
pos=-1;
}
if(t<=m)
{
if(lc==nullptr)
{
lc = new node1d;
lc->pos = t,lc->val = v;
}
else
lc-> update(s,m,t,v);
}
else
{
if(rc==nullptr)
{
rc= new node1d;
rc->pos = t,rc->val = v;
}
else
rc->update(m+1,e,t,v);
}
val =0;
if(lc!=nullptr)
val = __gcd(val,lc->val);
if(rc!=nullptr)
val = __gcd(val,rc->val);
}
ll query(int s,int e,int ts,int te)
{
if(te<s || e<ts)
return 0;
if(ts<=s && e<=te)
return val;
if(pos>=0)
{
if(ts<=pos && pos <=te)
return val;
return 0;
}
int m =(s+e)/2;
ll ret=0;
if(lc!=nullptr)
ret = __gcd(ret,lc->query(s,m,ts,te));
if(rc!=nullptr)
ret = __gcd(ret,rc->query(m+1,e,ts,te));
return ret;
}
};
struct node2d
{
node1d *T = new node1d;
node2d *lc=nullptr,*rc=nullptr;
void update(int s,int e,int tx,int ty,ll v)
{
if(e<tx || tx<s)
return ;
if(s==e)
{
T->update(0,C-1,ty,v);
return ;
}
int m = (s+e)/2;
if(tx<=m)
{
if(lc==nullptr)
lc = new node2d;
lc->update(s,m,tx,ty,v);
}
else
{
if(rc==nullptr)
rc = new node2d;
rc->update(m+1,e,tx,ty,v);
}
ll ret=0;
if(lc!=nullptr)
ret = __gcd(ret,lc->T->query(0,C-1,ty,ty));
if(rc!=nullptr)
ret = __gcd(ret,rc->T->query(0,C-1,ty,ty));
T->update(0,C-1,ty,ret);
}
ll query(int s,int e,int txs,int txe,int tys,int tye)
{
if(txe<s || e<txs)
return 0;
if(txs<=s && e<=txe)
return T->query(0,C-1,tys,tye);
int m = (s+e)/2;
ll ret=0;
if(lc!=nullptr)
ret = __gcd(ret,lc->query(s,m,txs,txe,tys,tye));
if(rc!=nullptr)
ret = __gcd(ret,rc->query(m+1,e,txs,txe,tys,tye));
return ret;
}
}*Seg = new node2d;
void init (int r,int c)
{
R=r,C=c;
}
void update(int x,int y,ll v)
{
Seg->update(0,R-1,x,y,v);
}
ll calculate(int x1,int y1,int x2,int y2)
{
return Seg->query(0,R-1,x1,x2,y1,y2);
}
