#include "game.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll gcd2(ll X, ll Y) {
while (X != Y && Y != 0) {
swap(X,Y);
Y %= X;
}
if(X == 1)return -1;
return X;
}
struct tree {
ll lb, rb, ub, db, val;
tree *ul, *ur, *bl, *br;
tree () : ul(NULL), ur(NULL), bl(NULL), br(NULL), val(0) {}
inline void initx(ll l, ll r, ll u, ll d){
lb = l, rb = r, ub = u, db = d;
}
inline void extend(int num){
ll mid1 = (lb+rb)>>1;
ll mid2 = (ub+db)>>1;
if(num == 0){
if(!ul){
ul = new tree;
ul->initx(lb,mid1,ub,mid2);
}
return;
}
if(num == 1){
if(!ur){
ur = new tree;
ur->initx(mid1+(lb == rb ? 0 : 1),rb,ub,mid2);
}
return;
}
if(num == 2){
if(!bl){
bl = new tree;
bl->initx(lb,mid1,mid2+(ub == db ? 0 : 1),db);
}
return;
}
if(!br){
br = new tree;
br->initx(mid1+(lb == rb ? 0 : 1),rb,mid2+(ub == db ? 0 : 1),db);
}
}
ll getGCD(ll l, ll r, ll u, ll d){
if(r < lb || rb < l || d < ub || db < u){
return 0;
}
if(l <= lb && rb <= r && u <= ub && db <= d){
return val;
}
ll mid11 = (lb+rb)>>1, mid22 = (db+ub)>>1;
ll ret = 0;
if(l <= mid11 && u <= mid22){if(ul)ret = gcd2(ret,ul->getGCD(l,r,u,d));}
if(ret == -1)return -1;
if(mid11 < r && u <= mid22){if(ur)ret = gcd2(ret,ur->getGCD(l,r,u,d));}
if(ret == -1)return -1;
if(l <= mid11 && mid22 < d){if(bl)ret = gcd2(ret,bl->getGCD(l,r,u,d));}
if(ret == -1)return -1;
if(mid11 < r && mid22 < d){if(br)ret = gcd2(ret,br->getGCD(l,r,u,d));}
return ret;
}
void chan(ll p1, ll p2, ll ne){
if(lb == rb && ub == db){
val = ne;
return;
}
ll ret = 0;
ll mid11 = (lb+rb)>>1, mid22 = (db+ub)>>1;
if(p1 <= mid11 && p2 <= mid22){extend(0);ul->chan(p1,p2,ne);}
else if(p2 <= mid22){extend(1);ur->chan(p1,p2,ne);}
else if(p1 <= mid11){extend(2);bl->chan(p1,p2,ne);}
else {extend(3);br->chan(p1,p2,ne);}
if(ul)ret = gcd2(ret,ul->val);
if(ur)ret = gcd2(ret,ur->val);
if(bl)ret = gcd2(ret,bl->val);
if(br)ret = gcd2(ret,br->val);
val = ret;
return;
}
};
tree *root = new tree();
void init(int R, int C) {
root->initx(0,C+2,0,R+2);
}
void update(int P, int Q, long long K) {
root->chan(Q,P,K);
}
long long calculate(int P, int Q, int U, int V) {
return abs(root->getGCD(Q,V,P,U));
}
