#include<bits//stdc++.h>
#include "game.h"
using namespace std;
using ll = long long;
long long GCD(long long X, long long Y) {
return(Y?GCD(Y,X%Y):X);
}
struct segment_tree{
int n;
vector<ll>seg;
segment_tree(){
}
void update(int i,ll x){
seg[i+=n]=x;
for(i/=2;i;i/=2)seg[i]=GCD(seg[i*2],seg[i*2+1]);
}
ll get(int l,int r){
ll ret=0;
for(l+=n,r+=n+1;l<r;l/=2,r/=2){
if(l&1)ret=GCD(ret,seg[l++]);
if(r&1)ret=GCD(ret,seg[--r]);
}
return ret;
}
};
struct segment_segment_tree{
int n;
vector<segment_tree>seg;
void comb(segment_tree&a,segment_tree&b,segment_tree&c){
for(int i=0;i<a.seg.size();++i)a.seg[i]=GCD(b.seg[i],c.seg[i]);
}
void update(int l,int r,int u,int R,int C,ll x){
if(l==r){
seg[u].update(C,x);
return;
}
int md=r+l>>1;
if(md<r)update(md+1,r,u*2+2,R,C,x);
else update(l,md,u*2+1,R,C,x);
comb(seg[u],seg[u*2+1],seg[u*2+2]);
}
ll get(int l,int r,int u,int P,int Q,int U,int V){
if(l>Q or U>r)return 0;
if(l>=P and r<=U)return seg[u].get(Q,V);
int md=r+l>>1;
return GCD(get(l,md,u*2+1,P,Q,U,V),get(md+1,r,u*2+2,P,Q,U,V));
}
};
segment_segment_tree seg;
void init(int R, int C) {
seg.seg.resize(R*4);
seg.n=R;
for(int i=0;i<R*4;++i){
seg.seg[i].seg.resize(2*C);
seg.seg[i].n=C;
}
}
void update(int P, int Q, long long K) {
seg.update(0,seg.n-1,0,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return seg.get(0,seg.n-1,0,P,Q,U,V);
}
