#include "game.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
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;
}
int r, c;
struct node{
int tl, tr;
ll val;
node *l = nullptr, *r = nullptr;
node(int tlval, int trval){
tl = tlval;
tr = trval;
val = 0;
}
node(){
}
void relax(){
if(l && l->val == 0){
delete l;
l = nullptr;
}
if(r && r->val == 0){
delete r;
r = nullptr;
}
}
void upd(int idx, ll nv){
if(tl == idx && tr == idx){
val = nv;
return;
}
int tm = (tl+tr)/2;
if(idx <= tm){
if(!l)
l = new node(tl, tm);
l->upd(idx, nv);
}
else{
if(!r)
r = new node(tm+1, tr);
r->upd(idx, nv);
}
ll xval = 0, yval = 0;
if(l)
xval = l->val;
if(r)
yval = r->val;
val = gcd2(xval, yval);
relax();
}
ll get(int lef, int rig){
if(tr < lef || rig < tl)
return 0;
if(lef <= tl && tr <= rig){
return val;
}
ll xval = 0, yval = 0;
if(l)
xval = l->get(lef, rig);
if(r)
yval = r->get(lef, rig);
return gcd2(xval, yval);
}
};
struct seg{
int tl, tr;
node *val;
seg *l = nullptr, *r = nullptr;
seg(ll tval, ll rval){
tl = tval;
tr = rval;
val = new node(0, c-1);
}
seg(){}
void upd(int xidx, int yidx, ll nv){
if(xidx < tl || xidx > tr) return;
if(tl == xidx && tr == xidx){
val->upd(yidx, nv);
return;
}
int tm = (tl+tr)/2;
if(xidx <= tm){
if(!l)
l = new seg(tl, tm);
l->upd(xidx, yidx, nv);
}
else{
if(!r)
r = new seg(tm+1, tr);
r->upd(xidx, yidx, nv);
}
ll xval = 0, yval = 0;
if(l)
xval = l->val->get(yidx, yidx);
if(r)
yval = r->val->get(yidx, yidx);
nv = gcd2(xval, yval);
val->upd(yidx, nv);
}
ll get(int xl, int xr, int yl, int yr){
if(tr < xl || xr < tl)
return 0;
if(xl <= tl && tr <= xr){
return val->get(yl, yr);
}
ll xval = 0, yval = 0;
if(l)
xval = l->get(xl, xr, yl, yr);
if(r)
yval = r->get(xl, xr, yl, yr);
return gcd2(xval, yval);
}
};
seg root;
void init(int R, int C) {
r = R;
c = C;
root = seg(0, r-1);
}
void update(int P, int Q, long long K) {
root.upd(P, Q, K);
}
long long calculate(int P, int Q, int U, int V){
return root.get(P, U, Q, V);
}
