#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct nodey {
nodey *l, *r;
ll val;
nodey(ll v) : l(nullptr), r(nullptr), val(v) {}
};
struct nodex {
nodex *l, *r;
nodey *nd;
nodex() : l(nullptr), r(nullptr), nd(nullptr) {}
};
nodex *rt=nullptr;
int r, c;
void psh(nodey *idx) {
idx->val=gcd((idx->l?idx->l->val : 0ll), (idx->r?idx->r->val : 0ll));
}
void updy(nodey *&idx, int u, ll val, int ql, int qr) {
if(!idx)
idx=new nodey(0);//
if(ql==qr) {
idx->val=val;
return;
}
int mid=(ql+qr)/2;
if(u<=mid)
updy(idx->l, u, val, ql, mid);
else
updy(idx->r, u, val, mid+1, qr);
psh(idx);
}
void updx(nodex *&idx, int p, int q, ll val, int ql, int qr) {
if(!idx)
idx=new nodex();
if(ql==qr) {
updy(idx->nd, q, val, 0, c-1);
return;
}
updy(idx->nd, q, val, 0, c-1);
int mid=(ql+qr)/2;
if(p<=mid)
updx(idx->l, p, q, val, ql, mid);
else
updx(idx->r, p, q, val, mid+1, qr);
}
ll qryy(nodey *&idx, int u, int v, int ql ,int qr) {
if(idx==nullptr)
return 0;
if(u<=ql&&qr<=v) {
return idx->val;
}
int mid=(ql+qr)/2;
ll res=0;
if(u<=mid)
res=gcd(res, qryy(idx->l, u, v, ql, mid));
if(mid<v)
res=gcd(res, qryy(idx->r, u, v, mid+1, qr));
return res;
}
ll qryx(nodex *&idx, int p, int q, int u, int v, int ql, int qr) {
if(idx==nullptr)
return 0;
if(p<=ql&&qr<=q) {
return qryy(idx->nd, u, v, 0, c-1);
}
int mid=(ql+qr)/2;
ll res=0;
if(p<=mid)
res=gcd(res, qryx(idx->l, p, q, u, v, ql, mid));
if(mid<q)
res=gcd(res, qryx(idx->r, p, q, u, v, mid+1, qr));
return res;
}
void init(int R, int C) {
r=R, c=C;
}
void update(int P, int Q, ll K) {
updx(rt, P, Q, K, 0, r-1);
}
ll calculate(int P, int Q, int U, int V) {
return qryx(rt, P, U, Q, V, 0, r-1);
}
