#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#define ll long long
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct nd{
ll val;
int l,r;
nd *ch[2];
nd(int L,int R){
l=L;r=R;
val=0;
ch[0]=NULL;
ch[1]=NULL;
}
void upd(int i,ll x){
if(l==r){
val=x;
}else{
int m=(l+r)/2;
if(i<=m){
if(!ch[0])ch[0]=new nd(l,m);
ch[0]->upd(i,x);
}else{
if(!ch[1])ch[1]=new nd(m+1,r);
ch[1]->upd(i,x);
}
val=0;
if(ch[0])val=gcd2(val,ch[0]->val);
if(ch[1])val=gcd2(val,ch[1]->val);
}
}
int qry(int l2,int r2){
if(l2<=l&&r<=r2)return val;
int m=(l+r)/2;
ll x=0;
if(ch[0]&&l2<=m)x=gcd2(x,ch[0]->qry(l2,r2));
if(ch[1]&&r2>m)x=gcd2(x,ch[1]->qry(l2,r2));
return x;
}
};
int n,m;
struct nd2{
nd *st;
int l,r;
nd2 *ch[2];
nd2(int L,int R){
l=L;
r=R;
st=new nd(0,m-1);
ch[0]=NULL;
ch[1]=NULL;
}
void upd(int i,int j,ll x){
if(l==r){
st->upd(j,x);
}else{
int m=(l+r)/2;
if(i<=m){
if(!ch[0])ch[0]=new nd2(l,m);
ch[0]->upd(i,j,x);
}else{
if(!ch[1])ch[1]=new nd2(m+1,r);
ch[1]->upd(i,j,x);
}
ll x=0;
if(ch[0])x=gcd2(x,ch[0]->st->qry(j,j));
if(ch[1])x=gcd2(x,ch[1]->st->qry(j,j));
st->upd(j,x);
}
}
ll qry(int r1,int c1,int r2,int c2){
if(r1<=l&&r<=r2)return st->qry(c1,c2);
int m=(l+r)/2;
ll x=0;
if(ch[0]&&r1<=m)x=gcd2(x,ch[0]->qry(r1,c1,r2,c2));
if(ch[1]&&r2>m)x=gcd2(x,ch[1]->qry(r1,c1,r2,c2));
return x;
}
};
nd2 *rt;
void init(int R, int C) {
n=R;
m=C;
rt=new nd2(0,n-1);
}
void update(int p, int q, long long x) {
rt->upd(p,q,x);
}
long long calculate(int r1,int c1,int r2, int c2) {
return rt->qry(r1,c1,r2,c2);
}
