#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pii = pair<int,int>;
const int T=40;
long long gcd2(long long X, long long Y) {
long long tmp;
if(X<Y) swap(X,Y);
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct n1{
n1 *lc,*rc;
ll x;
n1(){
lc=rc=nullptr;
x=0;
}
};
struct n2{
n2 *lc,*rc;
n1 *x;
n2(){
lc=rc=nullptr;
x=new n1;
}
} *rt=new n2;
int n,m;
map<pii,ll> mp;
void upd1(n1 *v, int l, int r, int p, ll x, int k = -1){
if(r-l<=T && k!=-1){
v->x=0;
for(int i=l; i<r; i++) if(mp.count({k,i})) v->x=gcd2(v->x,mp[{k,i}]);
return;
}
if(r-l==1){
v->x=x;
return;
}
int m=(l+r)>>1;
if(p<m){
if(!v->lc) v->lc=new n1;
upd1(v->lc,l,m,p,x,k);
}else{
if(!v->rc) v->rc=new n1;
upd1(v->rc,m,r,p,x,k);
}
v->x=0;
if(v->lc) v->x=gcd2(v->x,v->lc->x);
if(v->rc) v->x=gcd2(v->x,v->rc->x);
}
ll get1(n1 *v, int l, int r, int tl, int tr, int k = -1){
if(l>=tr || tl>=r || tl>=tr) return 0;
if(l>=tl && r<=tr) return v->x;
if(r-l<=T && k!=-1){
ll ans=0;
for(int i=l; i<r; i++) if(i>=tl && i<tr && mp.count({k,i})) ans=gcd2(ans,mp[{k,i}]);
return ans;
}
int m=(l+r)>>1;
ll ans=0;
if(v->lc) ans=gcd2(ans,get1(v->lc,l,m,tl,tr,k));
if(v->rc) ans=gcd2(ans,get1(v->rc,m,r,tl,tr,k));
return ans;
}
void upd2(n2 *v, int l, int r, int p, int q, ll x){
if(r-l==1){
upd1(v->x,0,m,q,x,l);
return;
}
int m=(l+r)>>1;
if(p<m){
if(!v->lc) v->lc=new n2;
upd2(v->lc,l,m,p,q,x);
}else{
if(!v->rc) v->rc=new n2;
upd2(v->rc,m,r,p,q,x);
}
ll y=0;
if(v->lc){
if(m-l==1) y=gcd2(y,get1(v->lc->x,0,::m,q,q+1,l));
else y=gcd2(y,get1(v->lc->x,0,::m,q,q+1));
}
if(v->rc){
if(r-m==1) y=gcd2(y,get1(v->rc->x,0,::m,q,q+1,m));
else y=gcd2(y,get1(v->rc->x,0,::m,q,q+1));
}
upd1(v->x,0,::m,q,y);
}
ll get2(n2 *v, int l, int r, int tl, int tr, int tp, int tq){
if(l>=tr || tl>=r || tl>=tr) return 0;
if(l>=tl && r<=tr){
if(r-l==1) return get1(v->x,0,m,tp,tq,l);
return get1(v->x,0,m,tp,tq);
}
int m=(l+r)>>1;
ll ans=0;
if(v->lc) ans=gcd2(ans,get2(v->lc,l,m,tl,tr,tp,tq));
if(v->rc) ans=gcd2(ans,get2(v->rc,m,r,tl,tr,tp,tq));
return ans;
}
void init(int R, int C) {
n=R;
m=C;
}
void update(int p, int q, long long k) {
mp[{p,q}]=k;
upd2(rt,0,n,p,q,k);
}
long long calculate(int p, int q, int u, int v) {
return get2(rt,0,n,p,u+1,q,v+1);
}
