#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 Node {
long long val; int l, r;
};
class RangedSegmentTree {
public:
vector<Node> I; int size_a, size_b, AX, AY, BX, BY;
void init(int H, int W) {
I.push_back(Node{0LL, -1, -1});
size_a = 1; while(size_a < H) size_a *= 2;
size_b = 1; while(size_b < W) size_b *= 2;
}
void update_(int cx, int cy, long long t, int ax, int ay, int bx, int by, int u) {
//cout << "cx = " << cx << ", cy = " << cy << ", t = " << t << ", ax = " << ax << ", ay = " << ay << ", bx = " << bx << ", by = " << by << ", u = " << u << endl;
if (by - ay == 1) {
I[u].val = t;
return;
}
if (bx - ax != 1) {
if (cx < ((ax + bx) >> 1)) {
if (I[u].l == -1) { I[u].l = I.size(); I.push_back(Node{0LL, -1, -1}); }
update_(cx, cy, t, ax, ay, (ax + bx) >> 1, by, I[u].l);
}
else {
if (I[u].r == -1) { I[u].r = I.size(); I.push_back(Node{0LL, -1, -1}); }
update_(cx, cy, t, (ax + bx) >> 1, ay, bx, by, I[u].r);
}
}
else {
if (cy < ((ay + by) >> 1)) {
if (I[u].l == -1) { I[u].l = I.size(); I.push_back(Node{0LL, -1, -1}); }
update_(cx, cy, t, ax, ay, bx, (ay + by) >> 1, I[u].l);
}
else {
if (I[u].r == -1) { I[u].r = I.size(); I.push_back(Node{0LL, -1, -1}); }
update_(cx, cy, t, ax, (ay + by) >> 1, bx, by, I[u].r);
}
}
long long B1 = 0; if(I[u].l >= 0) B1 = I[I[u].l].val;
long long B2 = 0; if(I[u].r >= 0) B2 = I[I[u].r].val;
I[u].val = gcd2(B1, B2);
return;
}
void update(int cx, int cy, long long t) {
update_(cx, cy, t, 0, 0, size_a, size_b, 0);
}
long long query_(int lx, int ly, int rx, int ry, int u) {
if (AX <= lx && rx <= BX && AY <= ly && ry <= BY) return I[u].val;
if (rx <= AX || BX <= lx || ry <= AY || BY <= ly) return 0;
if (rx - lx != 1) {
long long P1 = 0; if (I[u].l >= 0) P1 = query_(lx, ly, (lx + rx) >> 1, ry, I[u].l);
long long P2 = 0; if (I[u].r >= 0) P2 = query_((lx + rx) >> 1, ly, rx, ry, I[u].r);
return gcd2(P1, P2);
}
else {
long long P1 = 0; if (I[u].l >= 0) P1 = query_(lx, ly, rx, (ly + ry) >> 1, I[u].l);
long long P2 = 0; if (I[u].r >= 0) P2 = query_(lx, (ly + ry) >> 1, rx, ry, I[u].r);
return gcd2(P1, P2);
}
}
long long query(int ax, int ay, int bx, int by) {
AX = ax; AY = ay; BX = bx; BY = by;
return query_(0, 0, size_a, size_b, 0);
}
};
RangedSegmentTree Z;
void init(int R, int C) {
Z.init(R, C);
}
void update(int P, int Q, long long K) {
Z.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return Z.query(P, Q, U + 1, V + 1);
}
