#include "game.h"
#include "bits/stdc++.h"
using namespace std;
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;
}
struct st {
vector<long long> ar;
vector<int> le, ri;
int create_node() {
ar.push_back(0);
le.push_back(-1);
ri.push_back(-1);
return (int)ar.size() - 1;
}
void upd(int l, int r, int i, long long k, int v) {
if (l == i and i == r) {
ar[v] = k;
} else {
int mi = (l + r) / 2;
if (i <= mi) {
if (le[v] == -1) {
le[v] = create_node();
}
upd(l, mi, i, k, le[v]);
} else {
if (ri[v] == -1) {
ri[v] = create_node();
}
upd(mi + 1, r, i, k, ri[v]);
}
long long loc = 0;
if (le[v] != -1) {
loc = gcd2(loc, ar[le[v]]);
}
if (ri[v] != -1) {
loc = gcd2(loc, ar[ri[v]]);
}
ar[v] = loc;
}
}
long long qry(int l, int r, int a, int b, int v) {
if (a <= l and r <= b) {
return ar[v];
} else if (l <= b and a <= r) {
int mi = (l + r) / 2;
long long loc = 0;
if (le[v] != -1) {
loc = gcd2(loc, qry(l, mi, a, b, le[v]));
}
if (ri[v] != -1) {
loc = gcd2(loc, qry(mi + 1, r, a, b, ri[v]));
}
return loc;
} else {
return 0ll;
}
}
};
int n, m;
struct {
vector<st> ar;
vector<int> le, ri;
int create_node() {
ar.push_back({});
ar.back().create_node();
le.push_back(-1);
ri.push_back(-1);
return (int)ar.size() - 1;
}
void upd(int l, int r, int i, int j, int k, int v) {
if (l == i and i == r) {
ar[v].upd(0, m - 1, j, k, 0);
} else {
int mi = (l + r) / 2;
if (i <= mi) {
if (le[v] == -1) {
le[v] = create_node();
}
upd(l, mi, i, j, k, le[v]);
} else {
if (ri[v] == -1) {
ri[v] = create_node();
}
upd(mi + 1, r, i, j, k, ri[v]);
}
long long loc = 0;
if (le[v] != -1) {
loc = gcd2(loc, ar[le[v]].qry(0, m - 1, j, j, 0));
}
if (ri[v] != -1) {
loc = gcd2(loc, ar[ri[v]].qry(0, m - 1, j, j, 0));
}
ar[v].upd(0, m - 1, j, loc, 0);
}
}
long long qry(int l, int r, int a, int b, int p, int u, int v) {
if (a <= l and r <= b) {
return ar[v].qry(0, m - 1, p, u, 0);
} else if (a <= r and l <= b) {
int mi = (l + r) / 2;
long long loc = 0;
if (le[v] != -1) {
loc = gcd2(loc, qry(l, mi, a, b, p, u, le[v]));
}
if (ri[v] != -1) {
loc = gcd2(loc, qry(mi + 1, r, a, b, p, u, ri[v]));
}
return loc;
} else {
return 0ll;
}
}
} ot;
void init(int R, int C) {
n = R, m = C;
ot.create_node();
}
void update(int P, int Q, long long K) {
ot.upd(0, n - 1, P, Q, K, 0);
}
long long calculate(int P, int Q, int U, int V) {
return ot.qry(0, n - 1, P, U, Q, V, 0);
}
