#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<ll, ll> 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{
ll val = 0;
node *l = nullptr, *r = nullptr;
};
void upd1(node *root, int idx, ll nv, int tl, int tr){
if(tl == idx && tr == idx){
root->val = nv;
return;
}
int tm = (tl+tr)/2;
if(idx <= tm){
if(!root->l)
root->l = new node();
upd1(root->l, idx, nv, tl, tm);
}
else{
if(!root->r)
root->r = new node();
upd1(root->r, idx, nv, tm+1, tr);
}
ll xval = 0, yval = 0;
if(root->l)
xval = root->l->val;
if(root->r)
yval = root->r->val;
root->val = gcd2(xval, yval);
}
ll get1(node *root, int lef, int rig, int tl, int tr){
if(tr < lef || rig < tl)
return 0;
if(lef <= tl && tr <= rig){
return root->val;
}
ll xval = 0, yval = 0;
int tm = (tl+tr)/2;
if(root->l)
xval = get1(root->l, lef, rig, tl, tm);
if(root->r)
yval = get1(root->r, lef, rig, tm+1, tr);
return gcd2(xval, yval);
}
struct seg{
node *val;
seg *l = nullptr, *r = nullptr;
seg(){
val = new node();
}
};
void upd2(seg *root, int xidx, int yidx, ll nv, int tl, int tr){
if(xidx < tl || xidx > tr) return;
if(tl == xidx && tr == xidx){
upd1(root->val, yidx, nv, 0, c-1);
return;
}
int tm = (tl+tr)/2;
if(xidx <= tm){
if(!root->l)
root->l = new seg();
upd2(root->l, xidx, yidx, nv, tl, tm);
}
else{
if(!root->r)
root->r = new seg();
upd2(root->r, xidx, yidx, nv, tm+1, tr);
}
ll xval = 0, yval = 0;
if(root->l)
xval = get1(root->l->val, yidx, yidx, 0, c-1);
if(root->r)
yval = get1(root->r->val, yidx, yidx, 0, c-1);
nv = gcd2(xval, yval);
upd1(root->val, yidx, nv, 0, c-1);
}
ll get2(seg *root, int xl, int xr, int yl, int yr, int tl, int tr){
if(tr < xl || xr < tl)
return 0;
if(xl <= tl && tr <= xr){
return get1(root->val, yl, yr, 0, c-1);
}
ll xval = 0, yval = 0;
int tm = (tl+tr)/2;
if(root->l)
xval = get2(root->l, xl, xr, yl, yr, tl, tm);
if(root->r)
yval = get2(root->r, xl, xr, yl, yr, tm+1, tr);
return gcd2(xval, yval);
}
seg *root;
void init(int R, int C) {
r = R;
c = C;
root = new seg();
}
void update(int P, int Q, long long K) {
upd2(root,P, Q, K, 0, r-1);
}
long long calculate(int P, int Q, int U, int V){
return get2(root, P, U, Q, V, 0, r-1);
}
