#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;
struct Ty{
Ty* left;
Ty* right;
long long val;
Ty(){
this->left=NULL;
this->right=NULL;
this->val=0LL;
}
};
struct Tx{
Tx* left;
Tx* right;
Ty t;
Tx(){
this->left=NULL;
this->right=NULL;
this->t=Ty();
}
}*root;
void update2(Ty* node, int l, int r, int j, long long val){
if (l>j||r<j)
return;
if (l==r){
node->val=val;
return;
}
int mid=(l+r)>>1;
if (mid>=j){
if (node->left==NULL)
node->left=new Ty();
update2(node->left,l,mid,j,val);
}
else{
if (node->right==NULL&&mid<j)
node->right=new Ty();
update2(node->right,mid+1,r,j,val);
}
node->val=gcd2((node->left==NULL?0:node->left->val),(node->right==NULL?0:node->right->val));
}
long long get2(Ty* node, int l, int r, int u, int v){
if (node==NULL||l>v||r<u)
return 0;
if (l>=u&&r<=v)
return node->val;
int mid=(l+r)>>1;
return gcd2(get2(node->left,l,mid,u,v),get2(node->right,mid+1,r,u,v));
}
void update(Tx* node, int l, int r, int i, int j, long long val){
if (l==r){
update2(&node->t,0,c-1,j,val);
return;
}
int mid=(l+r)>>1;
if (mid>=i){
if (node->left==NULL)
node->left=new Tx();
update(node->left,l,mid,i,j,val);
}
else{
if (node->right==NULL)
node->right=new Tx();
update(node->right,mid+1,r,i,j,val);
}
update2(&node->t,0,c-1,j,gcd2(node->left?get2(&node->left->t,0,c-1,j,j):0,node->right?get2(&node->right->t,0,c-1,j,j):0));
}
long long get(Tx* node, int l, int r, int i, int j, int u, int v){
if (node==NULL||l>j||r<i)
return 0;
if (l>=i&&r<=j)
return get2(&node->t,0,c-1,u,v);
int mid=(l+r)>>1;
return gcd2(get(node->left,l,mid,i,j,u,v),get(node->right,mid+1,r,i,j,u,v));
}
void init(int R, int C){
r=R;
c=C;
root=new Tx();
}
void update(int P, int Q, long long K){
update(root,0,r-1,P,Q,K);
}
long long calculate(int P, int Q, int U, int V){
return get(root,0,r-1,P,U,Q,V);
}
