#include<bits/stdc++.h>
#include<game.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=2e5+3;
const int mod=1e9+7;
const int INF=1e18+7;
int n,q,a[maxn],boundr,boundc;
long long gcd(long long a,long long b)
{
if(b==0) return a;
return gcd(b,a%b);
}
struct segtreetree
{
struct segtree
{
struct node
{
long long val;
node *l,*r;
node(long long val): val(val),l(NULL),r(NULL){};
}*root;
long long vall(node* x) {return x?x->val:0;}
void update(node* kk,int cl,int cr,int pos,long long val)
{
if(cl==cr)
{
kk->val=val;
return;
}
int mid=(cl+cr)/2;
if(pos<=mid)
{
if(kk->l==NULL) kk->l=new node(0);
update(kk->l,cl,mid,pos,val);
}
else
{
if(kk->r==NULL) kk->r=new node(0);
update(kk->r,mid+1,cr,pos,val);
}
kk->val=gcd(vall(kk->l),vall(kk->r));
}
long long get(node* kk,int cl,int cr,int l,int r)
{
if(kk==NULL||cl>r||cr<l) return 0;
if(cl>=l&&cr<=r) return kk->val;
int mid=(cl+cr)/2;
return gcd(get(kk->l,cl,mid,l,r),get(kk->r,mid+1,cr,l,r));
}
segtree *l, *r;
segtree(): root(new node(0)), l(NULL), r(NULL) {};
}*root;
void update(segtree* kk,int cl,int cr,int r,int c,long long val)
{
kk->update(kk->root,0,boundc,c,val);
if(cl==cr)
{
return;
}
int mid=(cl+cr)/2;
if(r<=mid)
{
if(kk->l==NULL) kk->l=new segtree();
update(kk->l,cl,mid,r,c,val);
}
else
{
if(kk->r==NULL) kk->r=new segtree();
update(kk->r,mid+1,cr,r,c,val);
}
}
long long get(segtree *kk,int cl,int cr,int u,int l,int d,int r)
{
if(kk==NULL||cl>d||cr<u) return 0;
if(cl>=u&&cr<=d) return kk->get(kk->root,0,boundc,l,r);
int mid=(cl+cr)/2;
return gcd(get(kk->l,cl,mid,u,l,d,r),get(kk->r,mid+1,cr,u,l,d,r));
}
segtreetree(): root(new segtree()){};
}*root=new segtreetree();
void init(int R,int C)
{
boundr=R-1;
boundc=C-1;
}
void update(int P,int Q, long long k)
{
root->update(root->root,0,boundr,P,Q,k);
}
long long calculate(int P,int Q,int U,int V)
{
return root->get(root->root,0,boundr,P,Q,U,V);
}
