#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "game.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GCD(ll a,ll b) { return (a==0 && b==0) ? 0 : __gcd(a,b); }
struct treap
{
treap *left,*right;
ll key,prio,val,my_val;
treap(ll _key,ll _val) { key=_key; val=my_val=_val; prio=rng(); left=right=NULL; }
void comp()
{
val=GCD(my_val,GCD(left==NULL ? 0 : left->val,right==NULL ? 0 : right->val));
}
};
TII Split(treap *u,ll key)
{
if(u==NULL) return { NULL,NULL };
if(u->key>key)
{
TII x=Split(u->left,key);
u->left=x.snd;
u->comp();
return { x.fst,u };
}
else
{
TII x=Split(u->right,key);
u->right=x.fst;
u->comp();
return { u,x.snd };
}
}
treap *Merge(treap *u,treap *v)
{
if(u==NULL && v==NULL) return NULL;
if(u==NULL) return v;
if(v==NULL) return u;
if(u->prio>=v->prio)
{
u->right=Merge(u->right,v);
u->comp();
return u;
}
else
{
v->left=Merge(u,v->left);
v->comp();
return v;
}
}
ll get_range(treap *u,ll l,ll r)
{
TII x=Split(u,l-1);
TII y=Split(x.snd,r);
// cerr<<y.fst->key<<'\n';
ll res=(y.fst==NULL ? 0 : y.fst->val);
treap *tg=Merge(x.fst,y.fst);
Merge(tg,y.snd);
return res;
}
treap *Assign(treap *u,ll key,ll val)
{
TII x=Split(u,key-1);
TII y=Split(x.snd,key);
treap *v=new treap(key,val);
// get_range(v,key,key)<<'\n';
// exit(0);
u=Merge(x.fst,v);
// cerr<<get_range(u,val,val)<<'\n';
u=Merge(u,y.snd);
// cerr<<get_range(u,val,val)<<'\n';
return u;
}
////////////////////////////////////////////////////////////////////////
struct node
{
node *left,*right;
treap *tree;
} *root;
treap *get_tree(node *u) { return (u==NULL) ? NULL : u->tree; }
node *UPDATE(node *u,int l,int r,int x,int y,ll k)
{
if(u==NULL) u=new node();
if(l==r)
{
u->tree=Assign(u->tree,y,k);
return u;
}
int mid=(l+r)>>1;
if(x<=mid) u->left=UPDATE(u->left,l,mid,x,y,k);
else u->right=UPDATE(u->right,mid+1,r,x,y,k);
u->tree=Assign(u->tree,y,GCD(get_range(get_tree(u->left),y,y),get_range(get_tree(u->right),y,y)));
return u;
}
ll GET(node *u,int l,int r,int x1,int y1,int x2,int y2)
{
if(u==NULL || x1>r || x2<l) return 0;
if(x1<=l && r<=x2) return get_range(u->tree,y1,y2);
int mid=(l+r)>>1;
return GCD(GET(u->left,l,mid,x1,y1,x2,y2),GET(u->right,mid+1,r,x1,y1,x2,y2));
}
ll n,m,x,y,k,q,type;
void init(int _n,int _m) { n=_n; m=_m; }
void update(int x,int y,ll k)
{
root=UPDATE(root,1,n,x+1,y+1,k);
}
ll calculate(int x1,int y1,int x2,int y2)
{
return GET(root,1,n,x1+1,y1+1,x2+1,y2+1);
}
/*
int main()
{
freopen("game.inp","r",stdin);
freopen("game.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m>>q;
init(n,m);
while(cin>>type)
if(type==1) cin>>x>>y>>k,update(x,y,k);
else
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
cout<<calculate(x1,y1,x2,y2)<<'\n';
}
}
*/
