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