#include "game.h"
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;
}
struct SegTree{
struct Node{
int lb, rb, mid;
Node* l=0, *r=0;
long long val=0;
Node(int lb, int rb):lb(lb), rb(rb){mid=(lb+rb)/2;}
Node* get(int ind){
if(ind<=mid) return left();
else return right();
}
Node* left(){
if(l==0) l=new Node(lb, mid);
return l;
}
Node* right(){
if(r==0) r=new Node(mid+1, rb);
return r;
}
void set(int ind, long long v){
if(lb==ind && rb==ind){
val=v;
return;
}
get(ind)->set(ind, v);
if(l==0) val = r->val;
else if(r==0) val = l->val;
else val=gcd2(l->val, r->val);
}
long long query(int lft, int rgh){
if(lft<=lb && rgh>=rb) return val;
if(lb>rgh || rb<lft) return 0;
if(l==0 && r==0) return 0;
if(l==0) return r->query(lft, rgh);
if(r==0) return l->query(lft, rgh);
return gcd2(l->query(lft, rgh), r->query(lft, rgh));
}
};
Node *root;
SegTree(int n){root=new Node(0, n);}
void set(int ind, long long val){root->set(ind, val);}
long long query(int lb, int rb){return root->query(lb, rb);}
long long vl(int ind){return query(ind, ind);}
};
struct TDS{
struct Node{
int lb, rb, mid;
Node* l=0, *r=0;
SegTree val;
int n;
Node(int lb, int rb, int n):lb(lb), rb(rb), val(n), n(n) {mid=(lb+rb)/2;}
Node* get(int ind){
if(ind<=mid) return left();
else return right();
}
Node* left(){
if(l==0) l=new Node(lb, mid, n);
return l;
}
Node* right(){
if(r==0) r=new Node(mid+1, rb, n);
return r;
}
void set(int x, int y, long long v){
if(lb==x && rb==x){
val.set(y, v);
return;
}
get(x)->set(x, y, v);
if(l==0) val.set(y,r->val.vl(y));
else if(r==0) val.set(y, l->val.vl(y));
else val.set(y, gcd2(l->val.vl(y), r->val.vl(y)));
}
long long query(int lft, int rgh, int ylft, int yrgh){
if(lft<=lb && rgh>=rb) return val.query(ylft, yrgh);
if(lb>rgh || rb<lft) return 0;
if(l==0 && r==0) return 0;
if(l==0) return r->query(lft, rgh, ylft, yrgh);
if(r==0) return l->query(lft, rgh, ylft, yrgh);
return gcd2(l->query(lft, rgh, ylft, yrgh), r->query(lft, rgh, ylft, yrgh));
}
};
Node *root;
TDS(int x, int y){root=new Node(0, x, y+1);};
void set(int ind, int y, long long val){root->set(ind, y, val);}
long long query(int lb, int rb, int xl, int xr){return root->query(lb, rb, xl, xr);}
};
TDS* tree;
void init(int R, int C) {
tree=new TDS(R,C);
}
void update(int P, int Q, long long K) {
tree->set(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return tree->query(P,U,Q,V);
}
