#include "game.h"
#include <iostream>
int n, m, q;
const int XMAX = 300000;
const int YMAX = 9000000;
struct Nodey {
int l, r;
long long gcd;
} Y[YMAX];
long long ans = 0;
struct Nodex {
int l, r;
int root;
} X[XMAX];
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;
}
void updateY (int ind, int st, int dr, int a, long long k);
long long getVal (int nod, int b) {
long long ans = 0;
if (nod == 0)
return 0;
int root = X[nod].root;
int st = 1, dr = m;
while (root != 0) {
if (st == dr) {
return Y[root].gcd;
}
int mid = (st + dr) / 2;
if (mid >= b) {
root = Y[root].l;
dr = mid;
}
else {
root = Y[root].r;
st = mid + 1;
}
}
return 0;
}
int cntX, cntY;
void updateX (int ind, int st, int dr, int a, int b, long long k) {
if (ind == 0)
return;
Nodex &nod = X[ind];
if (st == dr) {
if (nod.root == 0)
nod.root = ++cntY;
updateY(nod.root, 1, m, b, k);
return;
}
int mid = (st + dr) / 2;
if (a <= mid) {
if (nod.l == 0)
nod.l = ++cntX;
updateX(nod.l, st, mid, a, b, k);
}
else {
if (nod.r == 0)
nod.r = ++cntX;
updateX(nod.r, mid + 1, dr, a, b, k);
}
if (nod.root == 0)
nod.root = ++cntY;
updateY(nod.root, 1, m, b, gcd2(getVal(nod.l, b), getVal(nod.r, b)));
}
void updateY (int ind, int st, int dr, int a, long long k) {
if (ind == 0)
return;
Nodey &nod = Y[ind];
if (st == dr) {
nod.gcd = k;
return;
}
int mid = (st + dr) / 2;
if (a <= mid) {
if (nod.l == 0)
nod.l = ++cntY;
updateY(nod.l, st, mid, a, k);
}
else {
if (nod.r == 0)
nod.r = ++cntY;
updateY(nod.r, mid + 1, dr, a, k);
}
nod.gcd = gcd2((nod.l == 0 ? 0 : Y[nod.l].gcd), (nod.r == 0 ? 0 : Y[nod.r].gcd));
}
void queryY(int ind, int st, int dr, int a, int b);
void queryX (int ind, int st, int dr, int a, int b, int c, int d) {
if (ind == 0)
return;
if (b < st || a > dr)
return;
Nodex &nod = X[ind];
if (a <= st && dr <= b) {
queryY(nod.root, 1, m, c, d);
return;
}
int mid = (st + dr) / 2;
queryX(nod.l, st, mid, a, b, c, d);
queryX(nod.r, mid + 1, dr, a, b, c, d);
}
void init (int R, int C) {
n = R;
m = C;
cntX = 1;
}
void queryY(int ind, int st, int dr, int a, int b) {
if (ind == 0)
return;
if (b < st || a > dr)
return;
Nodey &nod = Y[ind];
if (a <= st && dr <= b) {
ans = gcd2(ans, nod.gcd);
return;
}
int mid = (st + dr) / 2;
queryY(nod.l, st, mid, a, b);
queryY(nod.r, mid + 1, dr, a, b);
}
void update (int p, int q, long long k) {
p++; q++;
updateX(1, 1, n, p, q, k);
}
long long calculate (int x1, int y1, int x2, int y2) {
ans = 0;
x1 ++; y1++; x2++; y2++;
queryX(1, 1, n, x1, x2, y1, y2);
return ans;
}
