#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;
}
struct Node{
int x1, x2, y1, y2;
long long gcd = 0;
Node* dx[2] = {NULL};
Node* dy[2] = {NULL};
Node(int _x1, int _y1, int _x2, int _y2){
x1 = _x1;
y1 = _y1;
x2 = _x2;
y2 = _y2;
}
void update(int x, int y, long long val){
if(x1 == x2 && y1 == y2){
gcd = val;
return;
}
if(x1 != x2){
int m = (x1 + x2) >> 1;
if(dx[x > m] == NULL) dx[x > m] = new Node(x > m ? m + 1 : x1, y1, x > m ? x2 : m, y2);
dx[x > m] -> update(x, y, val);
gcd = gcd2(dx[0] == NULL ? 0 : dx[0] -> gcd, dx[1] == NULL ? 0 : dx[1] -> gcd);
}
if(y1 != y2){
int m = (y1 + y2) >> 1;
if(dy[y > m] == NULL) dy[y > m] = new Node(x1, y > m ? m + 1: y1, x2, y > m ? y2 : m);
dy[y > m] -> update(x, y, val);
gcd = gcd2(dy[0] == NULL ? 0 : dy[0] -> gcd, dy[1] == NULL ? 0 : dy[1] -> gcd);
}
}
long long query(int qx1, int qy1, int qx2, int qy2){
if(gcd == 0) return 0;
if(x1 == x2 && y1 == y2) return gcd;
if(qx1 == x1 && qx2 == x2 && qy1 == y1 && qy2 == y2) return gcd;
int mx = (x1 + x2) >> 1;
int my = (y1 + y2) >> 1;
if(x1 != x2){
if(mx >= qx2){
if(dx[0] == NULL) return 0;
return dx[0] -> query(qx1, qy1, qx2, qy2);
} else if(mx < qx1){
if(dx[1] == NULL) return 0;
return dx[1] -> query(qx1, qy1, qx2, qy2);
}
}
if(y1 != y2){
if(my >= qy2){
if(dy[0] == NULL) return 0;
return dy[0] -> query(qx1, qy1, qx2, qy2);
} else if(my < qy1){
if(dy[1] == NULL) return 0;
return dy[1] -> query(qx1, qy1, qx2, qy2);
}
}
if(x1 != x2){
return gcd2(dx[0] == NULL ? 0 : dx[0] -> query(qx1, qy1, mx, qy2), dx[1] == NULL ? 0 : dx[1] -> query(mx + 1, qy1, qx2, qy2));
}
return gcd2(dy[0] == NULL ? 0 : dy[0] -> query(qx1, qy1, qx2, my), dy[1] == NULL ? 0 : dy[1] -> query(qx1, my + 1, qx2, qy2));
}
} *root;
void init(int R, int C) {
root = new Node(0, 0, R - 1, C - 1);
}
void update(int P, int Q, long long K) {
root -> update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V){
return root -> query(P, Q, U, V);
}
