#include "game.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct NodeC {
ll val;
NodeC *l, *r;
NodeC() : val(0), l(nullptr), r(nullptr) {}
};
struct NodeR {
NodeC *root;
NodeR *l, *r;
NodeR() : root(nullptr), l(nullptr), r(nullptr) {}
};
int N, M;
NodeR *root;
void updC(NodeC *v, int l, int r, int a, ll x) {
if(a<l || a>r) return;
if(l==r) {
v->val=x;
return;
}
if(v->l==nullptr) v->l=new NodeC();
if(v->r==nullptr) v->r=new NodeC();
int mid=(l+r)/2;
updC(v->l, l, mid, a, x);
updC(v->r, mid+1, r, a, x);
v->val=gcd((v->l)->val, (v->r)->val);
}
ll cntC(NodeC *v, int l, int r, int a, int b) {
if(b<l || a>r) return 0;
if(a<=l && r<=b) return v->val;
int mid=(l+r)/2;
ll ans=0;
if(v->l!=nullptr) ans=gcd(ans, cntC(v->l, l, mid, a, b));
if(v->r!=nullptr) ans=gcd(ans, cntC(v->r, mid+1, r, a, b));
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(a<l || a>r) return;
if(l!=r) {
if(v->l==nullptr) v->l=new NodeR();
if(v->r==nullptr) v->r=new NodeR();
int mid=(l+r)/2;
updR(v->l, l, mid, a, b, x);
updR(v->r, mid+1, r, a, b, x);
x=gcd(cntC((v->l)->root, 0, M-1, b, b), cntC((v->r)->root, 0, M-1, b, b));
}
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;
}
int mid=(l+r)/2;
ll ans=0;
if(v->l!=nullptr) ans=gcd(ans, cntR(v->l, l, mid, ar, br, ac, bc));
if(v->r!=nullptr) ans=gcd(ans, cntR(v->r, mid+1, r, ar, br, ac, bc));
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);
}
