#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct node1d {
ll cgcd = 0;
node1d *l = 0, *r = 0;
node1d() {}
};
struct node2d {
node2d *l = 0, *r = 0;
node1d *seg = 0;
node2d() {}
} *root;
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;
void upd1d(node1d *&cur, int l, int r, int tgt, ll val) {
if(!cur) cur = new node1d();
if(l == r) {
cur->cgcd = val;
return ;
}
int mid = (l+r) >> 1;
if(tgt <= mid) upd1d(cur->l, l, mid, tgt, val);
else upd1d(cur->r, mid+1, r, tgt, val);
cur->cgcd = gcd2(cur->l ? cur->l->cgcd : 0, cur->r ? cur->r->cgcd: 0);
}
void upd2d(node2d *&cur, int l, int r, int tl, int tr, ll val) {
if(!cur) cur = new node2d();
if(l == r) {
upd1d(cur->seg, 0, C-1, tr, val);
return ;
}
int mid = (l+r) >> 1;
if(tl <= mid) upd2d(cur->l, l, mid, tl, tr, val);
else upd2d(cur->r, mid+1, r, tl, tr, val);
upd1d(cur->seg, 0, C-1, tr, val);
}
ll qr1d(node1d*&cur, int l, int r, int tl, int tr) {
if(!cur) return 0;
if(tr < l || r < tl) return 0;
if(tl <= l && r <= tr) return cur->cgcd;
int mid = (l+r) >> 1;
return gcd2(qr1d(cur->l, l, mid, tl, tr), qr1d(cur->r, mid+1, r, tl, tr));
}
ll qr2d(node2d *&cur, int l, int r, int tl1, int tr1, int tl2, int tr2) {
if(!cur) return 0;
if(tl1 <= l && r <= tr1) return qr1d(cur->seg, 0, C-1, tl2, tr2);
if(tr1 < l || r < tl1) return 0;
int mid = (l+r) >> 1;
return gcd2(qr2d(cur->l, l, mid, tl1, tr1, tl2, tr2), qr2d(cur->r, mid+1, r, tl1, tr1, tl2, tr2));
}
void init(int R, int C) {
/* ... */
::R = R; ::C = C;
root = 0;
}
void update(int P, int Q, long long K) {
/* ... */
upd2d(root, 0, R-1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
/* ... */
return qr2d(root, 0, R-1, P, U, Q, V);
}
