#include "game.h"
#include <stdio.h>
#include <stdlib.h>
#define lld long long
long long gcd2(long long X, long long Y) {
long long tmp;
if(X == 0) return Y;
if(Y == 0) return X;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct datay{
lld value;
datay *left,*right;
datay(){
value = 0;
left = right = NULL;
}
};
struct datax{
datax *left,*right;
datay *yroot;
datax(){
left = right = NULL;
}
}*xroot;
int R,C;
int nr,nc;
void init(int iR, int iC) {
R = iR; C = iC;
for(nr = 1; nr < R; nr *= 2);
for(nc = 1; nc < C; nc *= 2);
nr = R; nc = C;
xroot = new datax();
xroot -> yroot = new datay();
}
lld ans,value;
int findx,findy;
void yupdate1(datay *node,int left,int right){
if(left == right){
node -> value = value;
return;
}
int mid = (left+right)/2;
if(left <= findy && findy <= mid){
if(node -> left == NULL) node -> left = new datay();
yupdate1(node->left,left,mid);
}
if(mid+1 <= findy && findy <= right){
if(node -> right == NULL) node -> right = new datay();
yupdate1(node->right,mid+1,right);
}
if(node->left == NULL){
if(node->right == NULL) node->value = 0;
else node->value = (node->right)->value;
}else{
if(node->right == NULL) node->value = (node->left)->value;
else node->value = gcd2((node->left)->value,(node->right)->value);
}
}
void yclear(datay *node,int left,int right){
node -> value = 0;
if(left == right) return;
int mid = (left+right)/2;
if(left <= findy && findy <= mid){
if(node -> left == NULL) node -> left = new datay();
yclear(node->left,left,mid);
}
if(mid+1 <= findy && findy <= right){
if(node -> right == NULL) node -> right = new datay();
yclear(node->right,mid+1,right);
}
}
void yupdate2(datay *node,datay *node2,int left,int right){
node -> value = gcd2(node->value,node2->value);
if(left == right) return;
int mid = (left+right)/2;
if(left <= findy && findy <= mid && node2->left != NULL) yupdate2(node->left,node2->left,left,mid);
if(mid+1 <= findy && findy <= right && node2->right != NULL) yupdate2(node->right,node2->right,mid+1,right);
}
void xupdate(datax *node,int left,int right){
if(node -> yroot == NULL) node -> yroot = new datay();
if(left == right){
yupdate1(node -> yroot,1,nc);
return;
}
int mid = (left+right)/2;
if(left <= findx && findx <= mid){
if(node -> left == NULL) node -> left = new datax();
xupdate(node->left,left,mid);
}
if(mid+1 <= findx && findx <= right){
if(node -> right == NULL) node -> right = new datax();
xupdate(node->right,mid+1,right);
}
yclear(node->yroot,1,nc);
if(node -> left != NULL) yupdate2(node->yroot,(node->left)->yroot,1,nc);
if(node ->right != NULL) yupdate2(node->yroot,(node->right)->yroot,1,nc);
}
void update(int iP, int iQ, long long K) {
int P,Q;
P = iP; Q = iQ;
P++; Q++;
findx = P;
findy = Q;
value = K;
xupdate(xroot,1,nr);
}
int sx,ex,sy,ey;
bool crossy(int left,int right){
if(ey < left || right < sy) return false;
return true;
}
void ycalc(datay *node,int left,int right){
if(sy <= left && right <= ey){
ans = gcd2(ans,node->value);
return;
}
int mid = (left+right)/2;
if(crossy(left,mid) && node->left != NULL) ycalc(node->left,left,mid);
if(crossy(mid+1,right) && node->right != NULL) ycalc(node->right,mid+1,right);
}
bool crossx(int left,int right){
if(ex < left || right < sx) return false;
return true;
}
void xcalc(datax *node,int left,int right){
if(sx <= left && right <= ex){
ycalc(node->yroot,1,nc);
return;
}
int mid = (left+right)/2;
if(crossx(left,mid) && node -> left != NULL) xcalc(node->left,left,mid);
if(crossx(mid+1,right) && node -> right != NULL) xcalc(node->right,mid+1,right);
}
long long calculate(int iP, int iQ, int iU, int iV) {
int P,Q,U,V;
P = iP; Q = iQ; U = iU; V = iV;
P++; Q++; U++; V++;
ans = 0;
sx = P; ex = U;
sy = Q; ey = V;
xcalc(xroot,1,nr);
return ans;
}
