#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 check()
{
vector <pair <nodex*,ii> > processx;
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();
printf("%lld %d %d\n",currx->val,Lx,Rx);
vector <pair <nodey*,ii> > processy;
if(currx->Y!=0)
{
processy.pb(make_pair(currx->Y,ii(0,c-1)));
}
while(processy.size())
{
nodey* curry=processy.back().first;
int Ly=processy.back().second.first;
int Ry=processy.back().second.second;
processy.pop_back();
printf("%lld %d %d\n",curry->val,Ly,Ry);
if(curry->L!=0)
{
processy.pb(make_pair(curry->L,ii(Ly,(Ly+Ry)/2)));
}
if(curry->R!=0)
{
processy.pb(make_pair(curry->R,ii((Ly+Ry)/2+1,Ry)));
}
}
printf("\n");
if(currx->L!=0)
{
processx.pb(make_pair(currx->L,ii(Lx,(Lx+Rx)/2)));
}
if(currx->R!=0)
{
processx.pb(make_pair(currx->R,ii((Lx+Rx)/2+1,Rx)));
}
}
printf("\n");
}
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(Lx==Rx)
{
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);
}
}
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;
}
}
while(currx->par!=0)
{
currx=currx->par;
nodex* lx=currx->L;
nodex* rx=currx->R;
nodey* curry;
nodey* ly=0;
nodey* ry=0;
if(currx->Y==0)
{
currx->Y=new nodey;
currx->Y->parx=currx;
}
curry=currx->Y;
if(lx!=0)
{
ly=lx->Y;
}
if(rx!=0)
{
ry=rx->Y;
}
int Ly=0;
int Ry=c-1;
while(1)
{
ll ans=0;
if(ly!=0)
{
ans=ly->val;
}
if(ry!=0)
{
ans=gcd(ans,ry->val);
}
if(curry!=0)
{
curry->val=ans;
}
if(Ly==Ry)
{
break;
}
int My=(Ly+Ry)/2;
if(Q<=My)
{
if(curry->L==0)
{
curry->L=new nodey;
curry->L->par=curry;
}
curry=curry->L;
if(ly!=0)
{
ly=ly->L;
}
if(ry!=0)
{
ry=ry->L;
}
Ry=My;
}
else
{
if(curry->R==0)
{
curry->R=new nodey;
curry->R->par=curry;
}
curry=curry->R;
if(ly!=0)
{
ly=ly->R;
}
if(ry!=0)
{
ry=ry->R;
}
Ly=My+1;
}
}
}
//check();
}
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;
}
