#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
struct NodeY {
long long gcd;
NodeY *l, *r;
NodeY() : l(NULL), r(NULL), gcd(0) {}
};
struct NodeX {
int l, r;
NodeY *v;
NodeX() : l(0), r(0), v(NULL) {}
} a[70005];
int cnt = 1;
int R, C;
int P, Q, U, V;
long long K;
long long res;
void init(int _R, int _C) {
R = _R, C = _C;
}
void getY(NodeY *i, int l, int r) {
if (!i) return;
if (l > V || U > r) return;
if (U <= l && r <= V) {
res = __gcd(res, i -> gcd); return;
}
getY(i -> l, l, mid);
getY(i -> r, mid + 1, r);
}
void getX(int i, int l, int r) {
if (!i) return;
if (l > Q || P > r) return;
if (P <= l && r <= Q) {
getY(a[i].v, 0, C - 1); return;
}
getX(a[i].l, l, mid);
getX(a[i].r, mid + 1, r);
}
void updateY(NodeY *i, int l, int r) {
if (l == r) {
i -> gcd = K; return;
}
if (mid >= Q) {
if (!(i -> l)) i -> l = new NodeY();
updateY(i -> l, l, mid);
}
else {
if (!(i -> r)) i -> r = new NodeY();
updateY(i -> r, mid + 1, r);
}
long long vl = (!(i -> l) ? 0 : i -> l -> gcd);
long long vr = (!(i -> r) ? 0 : i -> r -> gcd);
i -> gcd = __gcd(vl, vr);
}
void updateX(int i, int l, int r) {
if (l == r) {
if (!(a[i].v)) a[i].v = new NodeY();
updateY(a[i].v, 0, C - 1);
return;
}
if (mid >= P) {
if (!(a[i].l)) a[i].l = ++cnt;
updateX(a[i].l, l, mid);
res = 0;
if (a[i].r) {
getY(a[a[i].r].v, 0, C - 1);
}
K = __gcd(K, res);
}
else {
if (!(a[i].r)) a[i].r = ++cnt;
updateX(a[i].r, mid + 1, r);
res = 0;
if (a[i].l) {
getY(a[a[i].l].v, 0, C - 1);
}
K = __gcd(K, res);
}
if (!(a[i].v)) a[i].v = new NodeY();
updateY(a[i].v, 0, C - 1);
}
void update(int _P, int _Q, long long _K) {
P = _P, Q = U = V = _Q, K = _K;
updateX(1, 0, R - 1);
}
long long calculate(int _P, int _U, int _Q, int _V) {
res = 0;
P = _P, Q = _Q, U = _U, V = _V;
getX(1, 0, R - 1);
return res;
}
