#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = long long;
ll n, m, q, k, x, y, a, b, c;
struct segtree {
vector<ll> tr;
vector<ll> ur, ul, dr, dl;
segtree() {
tr.assign(1, 0);
ur.assign(1, -1);
ul.assign(1, -1);
dr.assign(1, -1);
dl.assign(1, -1);
}
void extend(ll x) {
for (int i = 0; i < 4; i++) {
tr.push_back(0);
ul.push_back(-1);
ur.push_back(-1);
dl.push_back(-1);
dr.push_back(-1);
}
ul[x] = tr.size() - 4;
ur[x] = tr.size() - 3;
dl[x] = tr.size() - 2;
dr[x] = tr.size() - 1;
}
void update(ll x, ll lx, ll rx, ll ly, ll ry, ll X, ll Y, ll val) {
if (lx == rx && ly == ry) {
tr[x] = val;
return;
}
if (ur[x] == -1) {
extend(x);
}
ll midx = (rx + lx) / 2;
ll midy = (ry + ly) / 2;
if (X <= midx) {
if (Y <= midy) {
update(ul[x], lx, midx, ly, midy, X, Y, val);
}
else {
update(ur[x], lx, midx, midy + 1, ry, X, Y, val);
}
}
else {
if (Y <= midy) {
update(dl[x], midx + 1, rx, ly, midy, X, Y, val);
}
else {
update(dr[x], midx + 1, rx, midy + 1, ry, X, Y, val);
}
}
tr[x] = gcd(gcd(tr[ul[x]], tr[ur[x]]), gcd(tr[dl[x]], tr[dr[x]]));
}
ll query(ll x, ll lx, ll rx, ll ly, ll ry, ll LX, ll RX, ll LY, ll RY) {
if (x == -1) {
return 0;
}
if (tr[x] == 0) {
return 0;
}
if (rx < lx) {
return 0;
}
if (rx < LX) {
return 0;
}
if (RX < lx) {
return 0;
}
if (RX < LX) {
return 0;
}
if (ry < ly) {
return 0;
}
if (ry < LY) {
return 0;
}
if (RY < ly) {
return 0;
}
if (RY < LY) {
return 0;
}
if (LX <= lx && rx <= RX && LY <= ly && ry <= RY) {
return tr[x];
}
ll midx = (rx + lx) / 2;
ll midy = (ry + ly) / 2;
return gcd(
gcd(query(ul[x], lx, midx, ly, midy, LX, RX, LY, RY), query(ur[x], lx, midx, midy + 1, ry, LX, RX, LY, RY)),
gcd(query(dl[x], midx + 1, rx, ly, midy, LX, RX, LY, RY), query(dr[x], midx + 1, rx, midy + 1, ry, LX, RX, LY, RY))
);
}
};
segtree sg;
void init(int R, int C) {
n = R;
m = C;
sg = segtree();
}
void update(int P, int Q, long long K) {
sg.update(0, 0, n, 0, m, P, Q, K);
// cout << P << ' ' << Q << ' ' << K << endl;
}
long long calculate(int P, int Q, int U, int V) {
return sg.query(0, 0, n, 0, m, P, U, Q, V);
}
