#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int gcd2(int X, int Y) {
int tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int seg[4*2005][4*2005];
void updatey(int nx, int ny, int l, int r, int lx, int rx, int y, int v) {
if (l == r) {
if (lx == rx) {
seg[nx][ny] = v;
} else {
seg[nx][ny] = gcd2(seg[2*nx][ny], seg[2*nx+1][ny]);
}
} else {
int m = (l+r)/2;
if (l <= y && y <= m) {
updatey(nx, 2*ny, l, m, lx, rx, y, v);
} else {
updatey(nx, 2*ny+1, m+1, r, lx, rx, y, v);
}
seg[nx][ny] = gcd2(seg[nx][2*ny], seg[nx][2*ny+1]);
}
}
void updatex(int nx, int l, int r, int x, int y, int v) {
if (l != r) {
int m = (l+r)/2;
if (l <= x && x <= m) {
updatex(2*nx, l, m, x, y, v);
} else {
updatex(2*nx+1, m+1, r, x, y, v);
}
seg[nx][1] = gcd2(seg[2*nx][1], seg[2*nx+1][1]);
}
updatey(nx, 1, 0, 2000, l, r, y, v);
}
int queryy(int nx, int ny, int l, int r, int ay, int by) {
if (by < l || r < ay) {
return 0;
} else if (ay <= l && r <= by) {
return seg[nx][ny];
} else {
int m = (l+r)/2;
return gcd2(queryy(nx, 2*ny, l, m, ay, by), queryy(nx, 2*ny+1, m+1, r, ay, by));
}
}
int queryx(int nx, int l, int r, int ax, int bx, int ay, int by) {
if (bx < l || r < ax) {
return 0;
} else if (ax <= l && r <= bx) {
return queryy(nx, 1, 0, 2000, ay, by);
} else {
int m = (l+r)/2;
return gcd2(queryx(2*nx, l, m, ax, bx, ay, by), queryx(2*nx+1, m+1, r, ax, bx, ay, by));
}
}
void init(int32_t R, int32_t C) {
}
void update(int32_t P, int32_t Q, int K) {
updatex(1, 0, 2000, P, Q, K);
}
int calculate(int32_t P, int32_t Q, int32_t U, int32_t V) {
return queryx(1, 0, 2000, P, U, Q, V);
}
