#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=3e6;
const long long base=1000000001;
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;
}
int r,c,lx[sz],rx[sz],id;
vector <long long> st[sz];
vector <int> ly[sz],ry[sz];
unordered_map <long long, int> mp[sz];
void gen(int i){
st[i].emplace_back(0);
ly[i].emplace_back(-1);
ry[i].emplace_back(-1);
}
void update2(int node, int l, int r, int node2, int l2, int r2, int j, long long val){
//cout << ' ' << node << ' ' << l << ' ' << r << ' ' << node2 << ' ' << l2 << ' ' << r2 << ' ' << j << ' ' << val << '\n';
if (l2>j||r2<j||l2>r2)
return;
if (l2==r2){
if (l==r)
st[node][node2]=val;
else
st[node][node2]=gcd2((mp[lx[node]].count(base*l2+r2)?st[lx[node]][mp[lx[node]][base*l2+r2]]:0),(mp[rx[node]].count(base*l2+r2)?st[rx[node]][mp[rx[node]][base*l2+r2]]:0));
return;
}
int mid=(l2+r2)>>1;
if (ly[node][node2]==-1){
ly[node][node2]=st[node].size();
mp[node][base*l2+mid]=st[node].size();
gen(node);
}
if (ry[node][node2]==-1){
ry[node][node2]=st[node].size();
mp[node][base*(mid+1)+r2]=st[node].size();
gen(node);
}
update2(node,l,r,ly[node][node2],l2,mid,j,val);
update2(node,l,r,ry[node][node2],mid+1,r2,j,val);
st[node][node2]=gcd2(st[node][ly[node][node2]],st[node][ry[node][node2]]);
}
void update(int node, int l, int r, int i, int j, long long val){
if (l>i||r<i||l>r)
return;
if (l!=r){
int mid=(l+r)>>1;
if (lx[node]==-1){
id++;
lx[node]=id;
mp[node][c-1]=0;
gen(id);
}
if (rx[node]==-1){
id++;
rx[node]=id;
mp[node][c-1]=0;
gen(id);
}
update(lx[node],l,mid,i,j,val);
update(rx[node],mid+1,r,i,j,val);
}
update2(node,l,r,0,0,c-1,j,val);
}
long long get2(int node, int node2, int l, int r, int u, int v){
if (node2==-1||l>v||r<u||l>r)
return 0;
if (l>=u&&r<=v)
return st[node][node2];
int mid=(l+r)>>1;
return gcd2(get2(node,ly[node][node2],l,mid,u,v),get2(node,ry[node][node2],mid+1,r,u,v));
}
long long get(int node, int l, int r, int i, int j, int u, int v){
if (node==-1||l>j||r<i||l>r)
return 0;
if (l>=i&&r<=j)
return get2(node,0,0,c-1,u,v);
int mid=(l+r)>>1;
return gcd2(get(lx[node],l,mid,i,j,u,v),get(rx[node],mid+1,r,i,j,u,v));
}
void init(int R, int C){
memset(lx,-1,sizeof(lx));
memset(rx,-1,sizeof(rx));
gen(0);
r=R;
c=C;
}
void update(int P, int Q, long long K){
update(0,0,r-1,P,Q,K);
}
long long calculate(int P, int Q, int U, int V){
return get(0,0,r-1,P,U,Q,V);
}
