#include <bits/stdc++.h>
#include "game.h"
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ii = pair<int, int>;
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
ll R, C;
struct X{
X *lf, *rf; ll l, r; ll res;
X(ll s, ll e): l(s), r(e), lf(nullptr), rf(nullptr), res(0ll) {}
};
struct Y{
Y *lf, *rf; X node;
Y(): lf(nullptr), rf(nullptr), node(0, C - 1) {}
};
ll op(ll A, ll B) {
return __gcd(A, B);
}
void update(X *v, ll p, ll k) {
int l = v -> l, r = v -> r;
if(l == r) {
v -> res = k;
return;
}
ll md = (l + r) / 2;
if(p <= md) {
if(!v -> lf) v -> lf = new X(l, md);
update(v -> lf, p, k);
}
else {
if(!v -> rf) v -> rf = new X(md + 1, r);
update(v -> rf, p, k);
}
v -> res = op(v -> lf ? v -> lf -> res : 0,
v -> rf ? v -> rf -> res : 0);
}
ll query(X *v, ll l, ll r) {
if(!v || v -> l > r || v -> r < l) return 0ll;
if(v -> l >= l && v -> r <= r) return v -> res;
return op(query(v -> lf, l, r), query(v -> rf, l, r));
}
ll query(Y* V, ll l, ll r, ll p, ll q, ll u, ll v) {
if(!V || l > u || r < p) return 0;
if(l >= p && r <= u) return query(&V -> node, q, v);
ll md = (l + r) / 2;
return op(query(V -> lf, l, md, p, q, u, v),
query(V -> rf, md + 1, r, p, q, u, v));
}
void update(Y *v, ll l, ll r, ll x, ll y, ll k) {
ll md = (l + r) / 2;
if(l == r) {
update(&v -> node, y, k);
return;
}
if(x <= md) {
if(!v -> lf) v -> lf = new Y();
update(v -> lf, l, md, x, y, k);
}
else {
if(!v -> rf) v -> rf = new Y();
update(v -> rf, md + 1, r, x, y, k);
}
ll curr = op(
v -> lf ? query(&v -> lf -> node, y, y) : 0,
v -> rf ? query(&v -> rf -> node, y, y) : 0);
update(&v -> node, y, curr);
}
Y* root;
void init(int N, int M) {
R = N, C = M;
root = new Y();
}
void update(int P, int Q, ll K) {
update(root, 0, R - 1, P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return query(root, 0, R - 1, P, Q, U, V);
}
