#include <bits/stdc++.h>
using namespace std;
#include "game.h"
long long res;
struct node {
node *lp,*rp; long long x;
node() : lp(nullptr),rp(nullptr),x(0) {}
int update(int i,long long y,int ll,int rr){
if (i<ll||rr<=i) return x;
if (ll+1==rr) return x = gcd(x,y);
if (lp==nullptr) lp = new node();
if (rp==nullptr) rp = new node();
return x = gcd(lp->update(i,y,ll,(ll+rr)/2),rp->update(i,y,(ll+rr)/2,rr));
}
void query(int l,int r,int ll,int rr){
if (r<=ll||rr<=l) return;
if (l<=ll&&rr<=r) return (void)(res = gcd(res,x));
if (lp!=nullptr) lp->query(l,r,ll,(ll+rr)/2);
if (rp!=nullptr) rp->query(l,r,(ll+rr)/2,rr);
}
};
int h,w;
struct nnode {
nnode *lp,*rp; node x;
nnode() : lp(nullptr),rp(nullptr),x() {}
void update(int i,int k,long long y,int ll,int rr){
if (i<ll||rr<=i) return;
x.update(k,y,0,w);
if (ll+1==rr) return;
if (lp==nullptr) lp = new nnode();
if (rp==nullptr) rp = new nnode();
lp->update(i,k,y,ll,(ll+rr)/2),rp->update(i,k,y,(ll+rr)/2,rr);
}
void query(int l,int r,int i,int k,int ll,int rr){
if (r<=ll||rr<=l) return;
if (l<=ll&&rr<=r) return (void)x.query(i,k,0,w);
if (lp!=nullptr) lp->query(l,r,i,k,ll,(ll+rr)/2);
if (rp!=nullptr) rp->query(l,r,i,k,(ll+rr)/2,rr);
}
};
nnode segtree;
void init(int H,int W){
h = H,w = W;
}
void update(int i,int k,long long x){
segtree.update(i,k,x,0,h);
}
long long calculate(int a,int b,int c,int d){
res = 0,segtree.query(a,c+1,b,d+1,0,h);
return res;
}
