#include "game.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int base=10;
struct NodeC {
ll val=0;
NodeC *children[base]={};
};
struct NodeR {
NodeC *root=nullptr;
NodeR *children[base]={};
};
int N, M;
NodeR *root;
void updC(NodeC *v, int l, int r, int a, ll x) {
if(l==r) {
v->val=x;
return;
}
int p=(r-l)/base+1, akt=l;
v->val=0;
for(int i=0; akt<=r; ++i) {
if(akt<=a && a<=min(akt+p-1, r)) {
if(v->children[i]==nullptr) v->children[i]=new NodeC();
updC(v->children[i], akt, min(akt+p-1, r), a, x);
}
akt+=p;
if(v->children[i]!=nullptr) v->val=gcd(v->val, (v->children[i])->val);
}
}
ll cntC(NodeC *v, int l, int r, int a, int b) {
if(v==nullptr || b<l || a>r) return 0;
if(a<=l && r<=b) return v->val;
ll ans=0;
int p=(r-l)/base+1, akt=l;
for(int i=0; akt<=r; ++i) {
if(v->children[i]!=nullptr) {
ans=gcd(ans, cntC(v->children[i], akt, min(akt+p-1, r), a, b));
}
akt+=p;
}
return ans;
}
void updR(NodeR *v, int l, int r, int a, int b, ll x) {
if(v->root==nullptr) v->root=new NodeC();
if(l!=r) {
int p=(r-l)/base+1, akt=l;
for(int i=0; akt<=r; ++i) {
if(akt<=a && a<=min(akt+p-1, r)) {
if(v->children[i]==nullptr) v->children[i]=new NodeR();
updR(v->children[i], akt, min(akt+p-1, r), a, b, x);
}
akt+=p;
}
akt=l;
ll y=0;
for(int i=0; akt<=r; ++i) {
if(v->children[i]!=nullptr) {
y=gcd(y, cntC((v->children[i])->root, 0, M-1, b, b));
}
akt+=p;
}
x=y;
}
updC(v->root, 0, M-1, b, x);
}
ll cntR(NodeR *v, int l, int r, int ar, int br, int ac, int bc) {
if(br<l || ar>r) return 0;
if(ar<=l && r<=br) {
if(v->root!=nullptr) return cntC(v->root, 0, M-1, ac, bc);
return 0;
}
ll ans=0;
int p=(r-l)/base+1, akt=l;
for(int i=0; akt<=r; ++i) {
if(v->children[i]!=nullptr) {
ans=gcd(ans, cntR(v->children[i], akt, min(akt+p-1, r), ar, br, ac, bc));
}
akt+=p;
}
return ans;
}
void init(int R, int C) {
N=R;
M=C;
root=new NodeR();
}
void update(int a, int b, ll x) {
updR(root, 0, N-1, a, b, x);
}
ll calculate(int ar, int ac, int br, int bc) {
return cntR(root, 0, N-1, ar, br, ac, bc);
}
