#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;
}
int r, c;
int P, U, Q, V;
struct Y{
Y *ll = NULL, *rr = NULL;
long long val = 0;
};
void updateY(Y* y, int l, int r, long long K){
if(l == r){
y -> val = K;
return;
}
int m = (l + r) >> 1;
if(m < Q){
if(y -> rr == NULL) y -> rr = new Y();
updateY(y -> rr, m + 1, r, K);
} else {
if(y -> ll == NULL) y -> ll = new Y();
updateY(y -> ll, l, m, K);
}
y -> val = gcd2(y -> ll == NULL ? 0LL : y -> ll -> val, y -> rr == NULL ? 0LL : y -> rr -> val);
}
long long queryY(Y* y, int l, int r){
if(l > V || r < Q) return 0;
if(l >= Q && r <= V) return y -> val;
int m = (l + r) >> 1;
return gcd2(y -> ll == NULL ? 0LL : queryY(y -> ll, l, m), y -> rr == NULL ? 0LL : queryY(y -> rr, m + 1, r));
}
struct X{
X *ll = NULL, *rr = NULL;
Y *tree = new Y();
} *root = new X();
long long queryX(X *x, int l, int r){
if(l > U || r < P) return 0;
if(l >= P && r <= U) return x -> tree == NULL ? 0LL : queryY(x -> tree, 0, c);
int m = (l + r) >> 1;
return gcd2(x -> ll == NULL ? 0LL : queryX(x -> ll, l, m), x -> rr == NULL ? 0LL : queryX(x -> rr, m + 1, r));
}
void updateX(X *x, int l, int r, long long K){
if(l == r){
updateY(x -> tree, 0, c, K);
return;
}
int m = (l + r) >> 1;
if(m < P){
if(x -> rr == NULL) x -> rr = new X();
updateX(x -> rr, m + 1, r, K);
} else {
if(x -> ll == NULL) x -> ll = new X();
updateX(x -> ll, l, m, K);
}
updateY(x -> tree, 0, c, gcd2(x -> ll == NULL ? 0 : queryY(x -> ll -> tree, 0, c), x -> rr == NULL ? 0LL : queryY(x -> rr -> tree, 0, c)));
}
void init(int R, int C){
r = R - 1; c = C - 1;
};
void update(int P, int Q, long long K) {
::P = P; ::Q = Q; ::U = P; ::V = Q;
updateX(root, 0, r, K);
}
long long calculate(int P, int Q, int U, int V){
::P = P; ::Q = Q; ::U = U; ::V = V;
return queryX(root, 0, r);
}
