#include "game.h"
#include <bits/stdc++.h>
#pragma optimize("Ofast")
#pragma target("avx2")
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert
// #define int ll
const int MAX=10000+15;
const int N=104;
const ll inf=1e9;
const int mod=1e9+7;
const int mod1=1e9+9;
const ld eps=1e-9;
int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
int binpow(int a,int n){
if(!n)return 1;
if(n%2==1)return a*binpow(a,n-1)%mod;
int k=binpow(a,n/2);
return k*k%mod;
}
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
const int L=10;
map<pii,ll> t[MAX*L];
vector<int> ly[MAX*L],ry[MAX*L];
int cx=0;
int lx[MAX*L],rx[MAX*L];
int n,m;
void updatey(int vx,int xl,int xr,int v,int tl,int tr,int posx,int posy,ll x){
// cout<<vx<<" "<<xl<<" "<<xr<<" "<<v<<" "<<tl<<" "<<tr<<" "<<sz(t[vx])<<"\n";
// return;
if(tl==tr){
if(xl==xr){
t[vx][{tl,tr}]=x;
}
else{
t[vx][{tl,tr}]=0;
if(lx[vx]&&t[lx[vx]].count({tl,tr}))t[vx][{tl,tr}]=gcd2(t[vx][{tl,tr}],t[lx[vx]][{tl,tr}]);
if(rx[vx]&&t[rx[vx]].count({tl,tr}))t[vx][{tl,tr}]=gcd2(t[vx][{tl,tr}],t[rx[vx]][{tl,tr}]);
}
return;
}
int tm=(tl+tr)/2;
if(posy<=tm){
if(ly[vx][v]==0){
ly[vx][v]=sz(t[vx]);
t[vx][{tl,tm}]=0;
ly[vx].pb(0);
ry[vx].pb(0);
}
updatey(vx,xl,xr,ly[vx][v],tl,tm,posx,posy,x);
}
else{
if(ry[vx][v]==0){
ry[vx][v]=sz(t[vx]);
t[vx][{tm+1,tr}]=0;
ly[vx].pb(0);
ry[vx].pb(0);
}
updatey(vx,xl,xr,ry[vx][v],tm+1,tr,posx,posy,x);
}
t[vx][{tl,tr}]=0;
if(ly[vx][v])t[vx][{tl,tr}]=gcd2(t[vx][{tl,tr}],t[vx][{tl,tm}]);
if(ry[vx][v])t[vx][{tl,tr}]=gcd2(t[vx][{tl,tr}],t[vx][{tm+1,tr}]);
// cout<<xl<<" "<<xr<<" "<<tl<<" "<<tr<<" "<<t[vx][{tl,tr}]<<"\n";
}
void updatex(int v,int tl,int tr,int posx,int posy,ll x){
if(tl!=tr){
int tm=(tl+tr)/2;
if(posx<=tm){
if(lx[v]==0)lx[v]=++cx;
updatex(lx[v],tl,tm,posx,posy,x);
}
else{
if(rx[v]==0)rx[v]=++cx;
updatex(rx[v],tm+1,tr,posx,posy,x);
}
}
if(t[v].empty()){
t[v][{0,m}]=0;
ly[v].pb(0);
ry[v].pb(0);
}
updatey(v,tl,tr,0,0,m,posx,posy,x);
}
ll gety(int vx,int xl,int xr,int v,int tl,int tr,int l,int r){
if(l>r||tl>r||l>tr)return 0;
if(l<=tl&&tr<=r){
// cout<<v<<" "<<sz(t[vx])<<" "<<sz(ly[vx])<<" "<<sz(ry[vx])<<"\n";
// cout<<xl<<" "<<xr<<" "<<tl<<" "<<tr<<" "<<t[vx][v]<<"\n";
return t[vx][{tl,tr}];
}
int tm=(tl+tr)/2;
ll res=0;
if(ly[vx][v])res=gcd2(res,gety(vx,xl,xr,ly[vx][v],tl,tm,l,r));
if(ry[vx][v])res=gcd2(res,gety(vx,xl,xr,ry[vx][v],tm+1,tr,l,r));
return res;
}
ll getx(int v,int tl,int tr,int xl,int xr,int ly,int ry){
if(xl>xr||tl>xr||xl>tr)return 0;
if(xl<=tl&&tr<=xr){
if(!t[v].empty())return gety(v,xl,xr,0,0,m,ly,ry);
return 0;
}
int tm=(tl+tr)/2;
ll res=0;
if(lx[v])res=gcd2(res,getx(lx[v],tl,tm,xl,xr,ly,ry));
if(rx[v])res=gcd2(res,getx(rx[v],tm+1,tr,xl,xr,ly,ry));
return res;
}
void init(int R, int C) {
n=R-1;
m=C-1;
}
void update(int P, int Q, long long K) {
// return;
// cout<<K<<"\n";
updatex(0,0,n,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
// return 2;
int lx=min(P,U);
int rx=max(P,U);
int ly=min(Q,V);
int ry=max(Q,V);
// cout<<lx<<" "<<rx<<" "<<ly<<" "<<ry<<"\n";
// return 1;
return getx(0,0,n,lx,rx,ly,ry);
}
