#include "game.h"
#include<map>
#include<iostream>
#include<vector>
#include<algorithm>
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;
}
struct ura
{
int a,b;
long long value;
};
map<pair<int,int>,int>mp;
map<pair<int,int>,long long>realval;
int ids=0;
int invector[25000];
int buc[25000];
vector<ura>elem[205];
int top[205];
int bot[205];
vector<ura>pset;
vector<ura>nset;
int bucket=100;
int buckets;
int cb(int index,int value)
{
int st=0,dr=elem[index].size()-1;
while(st<=dr)
{
int mij=(st+dr)/2;
if(elem[index][mij].b>=value)
{
dr=mij-1;
}
else
{
st=mij+1;
}
}
return dr+1;
}
long long dp[205][205][205];
long long find(int index,int left,int right)
{
int i1=cb(index,left);
int i2=cb(index,right+1)-1;
if(i1<=i2)
{
return dp[index][i1][i2];
}
return 0;
}
void recalcbucket(int index)
{
for(int i=0; i<elem[index].size(); i++)
{
dp[index][i][i]=elem[index][i].value;
for(int j=i+1; j<elem[index].size(); j++)
{
dp[index][i][j]=gcd2(dp[index][i][j-1],elem[index][j].value);
}
}
}
void recalcvalue(int index,int a,int b,long long val)
{
for(int i=0; i<elem[index].size(); i++)
{
if(elem[index][i].a==a && elem[index][i].b==b)
{
elem[index][i].value=val;
}
}
recalcbucket(index);
}
void init(int R, int C)
{
buckets=0;
}
bool cmp(ura a,ura b)
{
return a.a<b.a;
}
bool cmp2(ura a,ura b)
{
return a.b<b.b;
}
void resetbuckets()
{
for(auto x:nset)
{
pset.push_back(x);
}
nset.clear();
sort(pset.begin(),pset.end(),cmp);
for(int i=1; i<=ids; i++)
{
invector[i]=1;
}
int cnt=0;
for(int z=0; z<pset.size()/bucket; z++)
{
elem[z].clear();
top[z]=1100000000;
bot[z]=0;
for(int i=0; i<bucket; i++)
{
pset[cnt].value=realval[{pset[cnt].a,pset[cnt].b}];
elem[z].push_back(pset[cnt]);
top[z]=min(top[z],pset[cnt].a);
bot[z]=max(bot[z],pset[cnt].a);
buc[mp[ {pset[cnt].a,pset[cnt].b}]]=z;
cnt++;
}
sort(elem[z].begin(),elem[z].end(),cmp2);
recalcbucket(z);
}
buckets=pset.size()/bucket;
}
void update(int P, int Q, long long K)
{
realval[{P,Q}]=K;
if(mp[ {P,Q}]==0)
{
ids++;
mp[ {P,Q}]=ids;
invector[ids]=0;
nset.push_back({P,Q,K});
if(nset.size()==bucket)
{
resetbuckets();
}
}
else
{
if(invector[mp[ {P,Q}]]==1)
{
recalcvalue(buc[mp[ {P,Q}]],P,Q,K);
}
else
{
for(int i=0; i<nset.size(); i++)
{
if(P==nset[i].a && Q==nset[i].b)
{
nset[i].value=K;
}
}
}
}
}
long long calculate(int P, int Q, int U, int V)
{
long long rez=0;
long long rez2=0;
/*
for(int i=0; i<nset2.size(); i++)
{
if(P<=nset2[i].a && nset2[i].a<=U && Q<=nset2[i].b && nset2[i].b<=V)
rez2=gcd2(rez2,nset2[i].value);
}*/
for(int i=0; i<nset.size(); i++)
{
if(P<=nset[i].a && nset[i].a<=U && Q<=nset[i].b && nset[i].b<=V)
rez=gcd2(rez,nset[i].value);
}
for(int i=0; i<buckets; i++)
{
if(P<=top[i] && bot[i]<=U)
{
rez=gcd2(rez,find(i,Q,V));
}
else if(P<=bot[i] || U>=top[i])
{
for(int j=0; j<elem[i].size(); j++)
{
if(P<=elem[i][j].a && elem[i][j].a<=U && Q<=elem[i][j].b && elem[i][j].b<=V)
{
rez=gcd2(rez,elem[i][j].value);
}
}
}
}
return rez;
}
