#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 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;
int n,m,q;
ll x,y,k,type,X1,Y1,X2,Y2;
ll GCD(ll a,ll b)
{
if(a==0 && b==0) return 0;
if(a==0) return b;
while(b>0)
{
ll r=a%b;
a=b;
b=r;
}
return a;
}
struct _1D_node
{
_1D_node *left,*right;
ll res=0;
void comp()
{
res=GCD(left==NULL ? 0 : left->res,right==NULL ? 0 : right->res);
}
};
_1D_node *get_left(_1D_node *u) { return (u==NULL) ? NULL : u->left; }
_1D_node *get_right(_1D_node *u) { return (u==NULL) ? NULL : u->right; }
ll get_res(_1D_node *u) { return (u==NULL) ? 0 : u->res; }
_1D_node *_1D_update(_1D_node *u,int l,int r)
{
if(u==NULL) u=new _1D_node();
if(l==r) { u->res=k; return u; }
int mid=(l+r)>>1;
if(y<=mid) u->left=_1D_update(u->left,l,mid);
else u->right=_1D_update(u->right,mid+1,r);
u->comp();
return u;
}
ll _1D_get(_1D_node *u,int l,int r)
{
if(Y1>r || Y2<l || u==NULL) return 0;
if(Y1<=l && r<=Y2) return u->res;
int mid=(l+r)>>1;
if(Y2<=mid) return _1D_get(u->left,l,mid);
if(Y1>mid) return _1D_get(u->right,mid+1,r);
return GCD(_1D_get(u->left,l,mid),_1D_get(u->right,mid+1,r));
}
_1D_node *_1D_comp(_1D_node *u,_1D_node *left,_1D_node *right,int l,int r)
{
if(u==NULL) u=new _1D_node();
u->res=GCD(get_res(left),get_res(right));
if(l==r) return u;
int mid=(l+r)>>1;
if(y<=mid) u->left=_1D_comp(u->left,get_left(left),get_left(right),l,mid);
else u->right=_1D_comp(u->right,get_right(left),get_right(right),mid+1,r);
return u;
}
struct _2D_node
{
_2D_node *left,*right;
_1D_node *Tree;
} *_2D_root;
_1D_node *get_Tree(_2D_node *u) { return (u==NULL ? NULL : u->Tree); }
_2D_node *_2D_update(_2D_node *u,int l,int r)
{
if(u==NULL) u=new _2D_node();
if(l==r) { u->Tree=_1D_update(u->Tree,1,m); return u; }
int mid=(l+r)>>1;
if(x<=mid) u->left=_2D_update(u->left,l,mid);
else u->right=_2D_update(u->right,mid+1,r);
u->Tree=_1D_comp(u->Tree,get_Tree(u->left),get_Tree(u->right),1,m);
return u;
}
ll _2D_get(_2D_node *u,int l,int r)
{
if(X1>r || X2<l || u==NULL) return 0;
if(X1<=l && r<=X2) return _1D_get(u->Tree,1,m);
int mid=(l+r)>>1;
return GCD(_2D_get(u->left,l,mid),_2D_get(u->right,mid+1,r));
}
void init(int _n,int _m)
{
n=_n; m=_m;
}
void update(int _x,int _y,ll _k)
{
x=_x+1; y=_y+1; k=_k;
_2D_root=_2D_update(_2D_root,1,n);
}
ll calculate(int _x1,int _y1,int _x2,int _y2)
{
X1=_x1+1; Y1=_y1+1; X2=_x2+1; Y2=_y2+1;
return _2D_get(_2D_root,1,n);
}
/*
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';
}
}
*/
