#include "game.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define pb push_back
#define __gcd gcd2
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 n, m;
unordered_map<ll, unordered_map<ll, ll> > tree;
vector<int> idcs;
void upd(int vx, int vy, int vlx, int vrx, int vly, int vry, int x, int y, ll val) {
if(vlx == vrx) {
if(vly == vry) {
idcs.pb(vy);
tree[vx][vy] = val;
return;
}
idcs.pb(vy);
int mid = (vly + vry) / 2;
if(y <= mid) {
upd(vx, 2 * vy, vlx, vrx, vly, mid, x, y, val);
} else {
upd(vx, 2 * vy + 1, vlx, vrx, mid + 1, vry, x, y, val);
}
tree[vx][vy] = __gcd(tree[vx][2 * vy], tree[vx][2 * vy + 1]);
return;
}
int mid = (vlx + vrx) / 2;
if(x <= mid) {
upd(2 * vx, vy, vlx, mid, vly, vry, x, y, val);
} else {
upd(2 * vx + 1, vy, mid + 1, vrx, vly, vry, x, y, val);
}
for(int idx : idcs) {
tree[vx][idx] = __gcd(tree[2 * vx][idx], tree[2 * vx + 1][idx]);
}
}
ll que(int vx, int vy, int vlx, int vrx, int vly, int vry, int qlx, int qrx, int qly, int qry) {
if(vlx == qlx && vrx == qrx) {
if(vly == qly && vry == qry) {
return tree[vx][vy];
}
if(vly > qry || vry < qly) {
return 0ll;
}
int mid = (vly + vry) / 2;
return __gcd(que(vx, 2 * vy, vlx, vrx, vly, mid, qlx, qrx, qly, min(qry, mid)),
que(vx, 2 * vy + 1, vlx, vrx, mid + 1, vry, qlx, qrx, max(qly, mid + 1), qry));
}
if(vlx > qrx || vrx < qlx) {
return 0ll;
}
int mid = (vlx + vrx) / 2;
return __gcd(que(2 * vx, vy, vlx, mid, vly, vry, qlx, min(qrx, mid), qly, qry),
que(2 * vx + 1, vy, mid + 1, vrx, vly, vry, max(qlx, mid + 1), qrx, qly, qry));
}
void init(signed R, signed C) {
n = R, m = C;
//
}
void update(signed P, signed Q, ll K) {
P++, Q++;
int x = P, y = Q;
ll val = K;
idcs.clear();
upd(1, 1, 1, n, 1, m, x, y, val);
}
ll calculate(signed P, signed Q, signed U, signed V) {
P++, Q++, U++, V++;
int a = P, b = Q, c = U, d = V;
ll res = 0;
res = que(1, 1, 1, n, 1, m, a, c, b, d);
return res;
}
