#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;
int R, C;
struct X{
X *lf, *rf; int l, r; ll res;
X(int s, int 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, int p, ll k) {
int l = v -> l, r = v -> r;
if(l == r) {
v -> res = k;
return;
}
int md = (l + r) / 2;
X **to = &(p <= md ? v -> lf : v -> rf);
if(!*to) {
*to = new X(p, p);
(*to) -> res = k;
}
else if((*to) -> l <= p && (*to) -> r >= p)
update(*to, p, k);
else {
while((p <= md) == ((*to) -> l <= md)) {
if(p <= md) r = md;
else l = md + 1;
md = (l + r) / 2;
}
X *node = new X(l, r);
if((*to) -> r <= md) node -> lf = *to;
else node -> rf = *to;
*to = node;
update(*to, p, k);
}
v -> res = op(v -> lf ? v -> lf -> res : 0,
v -> rf ? v -> rf -> res : 0);
}
ll query(X *v, int l, int 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));
}
void update(Y *v, int l, int r, int x, int y, ll k) {
int 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);
}
ll query(Y* V, int l, int r, int p, int q, int u, int v) {
if(!V || l > u || r < p) return 0;
if(l >= p && r <= u) return query(&V -> node, q, v);
int 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));
}
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);
}
