#include "game.h"
#include<map>
#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;
int ids=0;
int invector[25000];
int buc[25000];
vector<ura>elem[50];
int top[50];
int bot[50];
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;
}
int dp[50][205][205];
int 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) {
}
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);
}
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();
for(int i=0;i<bucket;i++)
{
elem[z].push_back(pset[cnt]);
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) {
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;
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;
}
