#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int R,C;
struct cnode{
int s,e;
cnode *left,*right;
long long val;
cnode(){
s=0;
e=C-1;
left=NULL;
right=NULL;
val=0;
}
cnode(int a, int b){
s=a;
e=b;
left=NULL;
right=NULL;
val=0;
}
};
struct rnode{
rnode *left, *right;
cnode ctree;
rnode(){
left=NULL;
right=NULL;
}
};
rnode root;
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;
}
long long query2(int s, int e, cnode *node){
if(node==NULL||node->s>e||node->e<s){
return 0;
}
if(s<=node->s&&node->e<=e){
return node->val;
}
return gcd2(query2(s,e,node->left),query2(s,e,node->right));
}
void update2(int col, cnode *node, long long k){
int l = node->s;
int r = node->e;
if(l==r){
node->val=k;
return;
}
int mid = (l+r)/2;
if(col<=mid){
//must go to left
if(node->left==NULL){
node->left = new cnode(col,col);
node->left->val = k;
}
else{
//node already exists check if range includes col
if(node->left->s<=col&&node->left->e>=col){
//includes just recurse
update2(col,node->left,k);
}
else{
//does not include. must make smallest parent.
while((col<=mid)==(node->left->s<=mid)){
if(col<=mid){
r=mid;
}
else{
l=mid+1;
}
mid=(l+r)/2;
}
cnode *newchild = new cnode(l,r);
if(node->left->s<=mid){
newchild->left=node->left;
node->left=newchild;
}
else{
newchild->right=node->left;
node->left=newchild;
}
update2(col,newchild,k);
}
}
}
else{
//must go to right
if(node->right==NULL){
node->right = new cnode(col,col);
node->right->val = k;
}
else{
//node already exists check if range includes col
if(node->right->s<=col&&node->right->e>=col){
//includes just recurse
update2(col,node->right,k);
}
else{
//does not include. must make smallest parent.
while((col<=mid)==(node->right->s<=mid)){
if(col<=mid){
r=mid;
}
else{
l=mid+1;
}
mid=(l+r)/2;
}
cnode *newchild = new cnode(l,r);
if(node->right->s<=mid){
newchild->left=node->right;
node->right=newchild;
}
else{
newchild->right=node->right;
node->right=newchild;
}
update2(col,newchild,k);
}
}
}
node->val = gcd2((node->left ? node->left->val : 0), (node->right ? node->right->val : 0));
}
void update1(int l, int r, int row, int col, rnode *node, long long k){
if(l==r){
update2(col,&(node->ctree),k);
return;
}
int mid = (l+r)/2;
if(row<=mid){
if(node->left==NULL){
node->left = new rnode();
}
update1(l,mid,row,col,node->left,k);
}
else{
if(node->right==NULL){
node->right = new rnode();
}
update1(mid+1,r,row,col,node->right,k);
}
update2(col,&(node->ctree),gcd2(
node->left ? query2(col,col,&(node->left->ctree)) : 0,
node->right ? query2(col,col,&(node->right->ctree)) : 0
));
}
long long query1(int l, int r, int u, int d, int s, int e, rnode *node){
if(node==NULL||r<u||l>d){
return 0;
}
if(u<=l&&r<=d){
return query2(s,e,&(node->ctree));
}
int mid = (l+r)/2;
return gcd2(query1(l,mid,u,d,s,e,node->left),query1(mid+1,r,u,d,s,e,node->right));
}
void init(int r, int c) {
/* ... */
R=r;
C=c;
root = *(new rnode());
}
void update(int p, int q, long long K) {
update1(0,R-1,p,q,&root,K);
}
long long calculate(int p, int q, int u, int v) {
return query1(0,R-1,p,u,q,v,&root);
}
