#include "game.h"
#include <bits/stdc++.h>
using namespace std;
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;
}
vector <long long> st,ul,ur,dl,dr;
void gen(){
st.emplace_back(0);
ul.emplace_back(-1);
ur.emplace_back(-1);
dl.emplace_back(-1);
dr.emplace_back(-1);
}
void update(int node, int l, int r, int l2, int r2, int i, int j, long long val){
if (l>i||r<i||l2>j||r2<j||l>r||l2>r2)
return;
if (l==r&&l2==r2){
st[node]=val;
return;
}
int mid=(l+r)>>1,mid2=(l2+r2)>>1;
if (ul[node]==-1){
ul[node]=st.size();
gen();
}
if (ur[node]==-1){
ur[node]=st.size();
gen();
}
if (dl[node]==-1){
dl[node]=st.size();
gen();
}
if (dr[node]==-1){
dr[node]=st.size();
gen();
}
update(ul[node],l,mid,l2,mid2,i,j,val);
update(ur[node],l,mid,mid2+1,r2,i,j,val);
update(dl[node],mid+1,r,l2,mid2,i,j,val);
update(dr[node],mid+1,r,mid2+1,r2,i,j,val);
st[node]=gcd2(gcd2(gcd2(st[ul[node]],st[ur[node]]),st[dl[node]]),st[dr[node]]);
}
long long get(int node, int l, int r, int l2, int r2, int i, int j, int u, int v){
if (node==-1||l>j||r<i||l2>v||r2<u||l>r||l2>r2)
return 0;
if (l>=i&&r<=j&&l2>=u&&r2<=v)
return st[node];
int mid=(l+r)>>1,mid2=(l2+r2)>>1;
long long a=get(ul[node],l,mid,l2,mid2,i,j,u,v);
long long b=get(ur[node],l,mid,mid2+1,r2,i,j,u,v);
long long c=get(dl[node],mid+1,r,l2,mid2,i,j,u,v);
long long d=get(dr[node],mid+1,r,mid2+1,r2,i,j,u,v);
return gcd2(gcd2(gcd2(a,b),c),d);
}
int r,c;
void init(int R, int C){
st.reserve(80000000);
gen();
r=R;
c=C;
}
void update(int P, int Q, long long K) {
update(0,0,r-1,0,c-1,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return get(0,0,r-1,0,c-1,P,U,Q,V);
}
