#include"game.h"
#include<vector>
#include<iostream>
using namespace std;
typedef long long ll;
const int TREE_SIZE=1<<30;
ll gcd2(ll X,ll Y){
ll tmp;
while (X!=Y&&Y!=0){
tmp=X;
X=Y;
Y=tmp%Y;
}
return X;
}
struct Tree1{
ll val;
Tree1*ch1,*ch2;
Tree1():val(0),ch1(0),ch2(0){}
};
ll tree1_get_val(Tree1*node){
if(node==nullptr)
return 0;
return node->val;
}
Tree1*tree1_set(Tree1*node,int rl,int rr,int i,int v){
if(node==nullptr)
node=new Tree1;
if(rl==rr-1){
node->val=v;
return node;
}
int mid=(rl+rr)/2;
if(i<mid){
node->ch1=tree1_set(node->ch1,rl,mid,i,v);
}else{
node->ch2=tree1_set(node->ch2,mid,rr,i,v);
}
node->val=gcd2(tree1_get_val(node->ch1),tree1_get_val(node->ch2));
return node;
}
ll tree1_get(Tree1*node,int rl,int rr,int x1,int x2){
if(node==nullptr)
return 0;
if(x2<=rl||rr<=x1)
return 0;
if(x1<=rl&&rr<=x2)
return node->val;
int mid=(rl+rr)/2;
return gcd2(tree1_get(node->ch1,rl,mid,x1,x2),tree1_get(node->ch2,mid,rr,x1,x2));
}
vector<Tree1>trees;
void init(int h,int w){
trees=vector<Tree1>(h);
}
void update(int y,int x,ll v){
tree1_set(&trees[y],0,TREE_SIZE,x,v);
}
ll calculate(int y1,int x1,int y2,int x2){
y2++;
x2++;
ll res=0;
for(int y=y1;y<y2;y++)
res=gcd2(res,tree1_get(&trees[y],0,TREE_SIZE,x1,x2));
return res;
}
