#include "game.h"
#define gcd gcd2
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef pair <int,int> ii;
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 nodex;
struct nodey
{
nodey* L=0;
nodey* R=0;
nodey* par=0;
nodex* parx=0;
ll val=0;
};
struct nodex
{
nodex* L=0;
nodex* R=0;
nodex* par=0;
nodey* Y=0;
ll val=0;
};
int r;
int c;
nodex* segment_tree;
void init(int R, int C)
{
r=R;
c=C;
segment_tree=new nodex;
}
void update(int P, int Q, long long K)
{
nodex* currx=segment_tree;
int Lx=0;
int Rx=r-1;
while(1)
{
if(currx->Y==0)
{
currx->Y=new nodey;
currx->Y->parx=currx;
}
nodey* curry=currx->Y;
int Ly=0;
int Ry=c-1;
while(1)
{
if(Ly==Ry)
{
curry->val=K;
break;
}
int My=(Ly+Ry)/2;
if(Q<=My)
{
if(curry->L==0)
{
curry->L=new nodey;
curry->L->par=curry;
}
curry=curry->L;
Ry=My;
}
else
{
if(curry->R==0)
{
curry->R=new nodey;
curry->R->par=curry;
}
curry=curry->R;
Ly=My+1;
}
}
while(1)
{
if(curry->par==0)
{
break;
}
curry=curry->par;
curry->val=0;
if(curry->L!=0)
{
curry->val=curry->L->val;
}
if(curry->R!=0)
{
curry->val=gcd(curry->val,curry->R->val);
}
}
currx->val=currx->Y->val;
if(Lx==Rx)
{
break;
}
int Mx=(Lx+Rx)/2;
if(P<=Mx)
{
if(currx->L==0)
{
currx->L=new nodex;
currx->L->par=currx;
}
currx=currx->L;
Rx=Mx;
}
else
{
if(currx->R==0)
{
currx->R=new nodex;
currx->R->par=currx;
}
currx=currx->R;
Lx=Mx+1;
}
}
}
long long calculate(int P, int Q, int U, int V)
{
ll ans=0;
vector <pair <nodex*,ii> > processx;
vector <pair <nodey*,ii> > processy;
processx.pb(make_pair(segment_tree,ii(0,r-1)));
while(processx.size())
{
nodex* currx=processx.back().first;
int Lx=processx.back().second.first;
int Rx=processx.back().second.second;
processx.pop_back();
int Mx=(Lx+Rx)/2;
if(P<=Lx && Rx<=U)
{
if(currx->Y!=0)
{
processy.pb(make_pair(currx->Y,ii(0,c-1)));
}
continue;
}
if(P<=Mx)
{
if(currx->L!=0)
{
processx.pb(make_pair(currx->L,ii(Lx,Mx)));
}
}
if(Mx+1<=U)
{
if(currx->R!=0)
{
processx.pb(make_pair(currx->R,ii(Mx+1,Rx)));
}
}
}
while(processy.size())
{
nodey* curry=processy.back().first;
int Ly=processy.back().second.first;
int Ry=processy.back().second.second;
processy.pop_back();
int My=(Ly+Ry)/2;
if(Q<=Ly && Ry<=V)
{
ans=gcd(ans,curry->val);
continue;
}
if(Q<=My)
{
if(curry->L!=0)
{
processy.pb(make_pair(curry->L,ii(Ly,My)));
}
}
if(My+1<=V)
{
if(curry->R!=0)
{
processy.pb(make_pair(curry->R,ii(My+1,Ry)));
}
}
}
return ans;
}
