#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = int;
ll n, m, q, k, x, y, a, b, c;
struct segtree1d {
vector<long long> tr;
vector<ll> pl, pr;
segtree1d() {
tr.assign(1, 0);
pl.assign(1, -1);
pr.assign(1, -1);
}
void extend(ll x) {
for (int i = 0; i < 2; i++) {
tr.push_back(0);
pl.push_back(-1);
pr.push_back(-1);
}
pl[x] = tr.size() - 2;
pr[x] = tr.size() - 1;
}
void update(ll x, ll l, ll r, ll idx, long long val) {
// cout << x << ' ' << l << ' ' << r << ' ' << ' ' << idx << ' ' << val << '\n';
if (l == r) {
tr[x] = val;
return;
}
if (pl[x] == -1) {
extend(x);
}
ll mid = (r + l) / 2;
if (idx <= mid) {
update(pl[x], l, mid, idx, val);
}
else {
update(pr[x], mid + 1, r, idx, val);
}
tr[x] = gcd(tr[pl[x]], tr[pr[x]]);
}
long long query(ll x, ll l, ll r, ll L, ll R) {
if (r < l) {
return 0;
}
if (r < L) {
return 0;
}
if (R < l) {
return 0;
}
if (R < L) {
return 0;
}
if (L <= l && r <= R) {
return tr[x];
}
if (pl[x] == -1) {
extend(x);
}
ll mid = (r + l) / 2;
return gcd(query(pl[x], l, mid, L, R), query(pr[x], mid + 1, r, L, R));
}
};
struct segtree {
vector<segtree1d> tr;
vector<ll> pl, pr;
segtree() {
tr.assign(1, segtree1d());
pl.assign(1, -1);
pr.assign(1, -1);
}
void extend(ll x) {
for (int i = 0; i < 2; i++) {
tr.push_back(segtree1d());
pl.push_back(-1);
pr.push_back(-1);
}
pl[x] = tr.size() - 2;
pr[x] = tr.size() - 1;
}
void update(ll x, ll l, ll r, ll X, ll Y, long long val) {
// cout << x << ' ' << l << ' ' << r << ' ' << ' ' << X << ' ' << Y << ' ' << val << '\n';
if (l == r) {
tr[x].update(0, 0, m, Y, val);
return;
}
if (pl[x] == -1) {
extend(x);
}
ll mid = (r + l) / 2;
if (X <= mid) {
update(pl[x], l, mid, X, Y, val);
}
else {
update(pr[x], mid + 1, r, X, Y, val);
}
tr[x].update(0, 0, m, Y, gcd(tr[pl[x]].query(0, 0, m, Y, Y), tr[pr[x]].query(0, 0, m, Y, Y)));
}
long long query(ll x, ll l, ll r, ll LX, ll RX, ll LY, ll RY) {
if (r < l) {
return 0;
}
if (r < LX) {
return 0;
}
if (RX < l) {
return 0;
}
if (RX < LX) {
return 0;
}
if (LX <= l && r <= RX) {
return tr[x].query(0, 0, m, LY, RY);
}
if (pl[x] == -1) {
extend(x);
}
ll mid = (r + l) / 2;
return gcd(query(pl[x], l, mid, LX, RX, LY, RY), query(pr[x], mid + 1, r, 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, P, Q, K);
// cout << '\n';
// cout << P << ' ' << Q << ' ' << K << endl;
}
long long calculate(int P, int Q, int U, int V) {
return sg.query(0, 0, n, P, U, Q, V);
}
