#include"game.h"
#include<bits/stdc++.h>
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 node
{
vector<int> child[2];
vector<long long> seg;
int cntnode;
void init()
{
seg.resize(3),child[0].resize(3),child[1].resize(3),cntnode=1;
}
void update(int x,long long val)
{
int pos=1;
vector<int> vi;
for(int i=29;i+1;i--)
{
int a=(x>>i)%2;
if(!child[a][pos]) child[a][pos]=++cntnode,child[0].push_back(0),child[1].push_back(0),seg.push_back(0);
vi.push_back(pos),pos=child[a][pos];
}
seg[pos]=val;
while(!vi.empty())
{
int a=vi.back();
vi.pop_back(),seg[a]=gcd2(seg[child[0][a]],seg[child[1][a]]);
}
}
long long get(int l,int r,int u,int v,int pos)
{
if(u<=l&&r<=v) return seg[pos];
int mid=(l+r)/2;
long long a=0,b=0;
if(u<=mid)
{
if(child[0][pos]) a=get(l,mid,u,v,child[0][pos]);
else a=0;
}
if(mid+1<=v)
{
if(child[1][pos]) b=get(mid+1,r,u,v,child[1][pos]);
else b=0;
}
return gcd2(a,b);
}
};
int child[676767][2],cntnode=1;
node A[676767];
long long get(int l,int r,int u,int v,int p,int q,int pos)
{
if(u<=l&&r<=v) return A[pos].get(0,(1<<30)-1,p,q,1);
int mid=(l+r)/2;
long long a=0,b=0;
if(u<=mid)
{
if(child[pos][0]) a=get(l,mid,u,v,p,q,child[pos][0]);
else a=0;
}
if(mid+1<=v)
{
if(child[pos][1]) b=get(mid+1,r,u,v,p,q,child[pos][1]);
else b=0;
}
return gcd2(a,b);
}
void init(int R,int C)
{
A[1].init();
}
void update(int x,int y,long long val)
{
int pos=1;
for(int i=29;i+1;i--)
{
int a=(x>>i)%2;
if(!child[pos][a]) child[pos][a]=++cntnode,A[cntnode].init();
A[pos].update(y,val),pos=child[pos][a];
}
A[pos].update(y,val);
}
long long calculate(int P,int Q,int U,int V)
{
return get(0,(1<<30)-1,P,U,Q,V,1);
}
