#include "game.h"
long long gcd(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
const int maxn = 111;
long long tree[4100][4100], n, m;
void updateY(int ndx, int lx, int rx, int ndy, int ly, int ry, int y, long long val) {
if(ly == ry) {
if(lx == rx) tree[ndx][ndy] = val;
else tree[ndx][ndy] = gcd(tree[ndx*2][ndy], tree[ndx*2+1][ndy]);
return;
} int mid = ly + ry >> 1;
if(y <= mid) updateY(ndx, lx, rx, ndy*2, ly, mid, y, val);
else updateY(ndx, lx, rx, ndy*2+1, mid+1, ry, y, val);
tree[ndx][ndy] = gcd(tree[ndx][ndy*2], tree[ndx][ndy*2+1]);
}
void updateX(int ndx, int lx, int rx, int x, int y, long long val) {
if(lx != rx) {
int mid = lx + rx >> 1;
if(x <= mid) updateX(ndx*2, lx, mid, x, y, val);
else updateX(ndx*2+1, mid+1, rx, x,y, val);
} updateY(ndx, lx, rx, 1, 0, m-1, y,val);
}
long long queryY(int ndx, int ndy, int ly, int ry, int y1, int y2) {
if(ry < y1 || ly > y2) return 0;
if(y1 <= ly && ry <= y2)
return tree[ndx][ndy];
int mid = ly + ry >> 1;
return gcd(queryY(ndx, ndy*2, ly, mid, y1, y2),
queryY(ndx, ndy*2+1, mid+1, ry, y1, y2));
}
long long queryX(int ndx, int lx, int rx, int x1, int y1, int x2, int y2) {
if(rx < x1 || lx > x2) return 0;
if(x1 <= lx && rx <= x2) {
return queryY(ndx, 1, 0, m-1, y1, y2);
} int mid = lx + rx >> 1;
return gcd(queryX(ndx*2, lx, mid, x1,y1,x2,y2),
queryX(ndx*2+1, mid+1, rx, x1,y1,x2,y2));
}
void init(int R, int C) {
n = R, m = C;
}
void update(int P, int Q, long long K) {
updateX(1, 0, n-1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return queryX(1, 0, n-1, P,Q,U,V);
}
