#include <bits/stdc++.h>
using namespace std;
#include "game.h"
struct node{
node *l=NULL;
node *r=NULL;
node *seg=NULL;
long long gcd=0;
};
node* root;
int offset=(1<<30);
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;
}
void upd2(node* cur,int c,int lo,int hi,long long val){
if(lo==c && hi==c){
cur->gcd=val;
return;
}
if(lo>c || hi<c)return;
int mid=(lo+hi)/2;
if(mid>=c){
if(cur->l==NULL)cur->l=new node;
upd2(cur->l,c,lo,mid,val);
}
else{
if(cur->r==NULL)cur->r=new node;
upd2(cur->r,c,mid+1,hi,val);
}
cur->gcd=gcd2((cur->l==NULL?0:cur->l->gcd),(cur->r==NULL?0:cur->r->gcd));
}
long long query2(node* cur,int c1,int c2,int lo,int hi){
if(lo>=c1 && hi<=c2)return cur->gcd;
if(lo>c2 || hi<c1)return 0;
int mid=(lo+hi)/2;
long long x=0,y=0;
if(cur->l!=NULL)x=query2(cur->l,c1,c2,lo,mid);
if(cur->r!=NULL)y=query2(cur->r,c1,c2,mid+1,hi);
return gcd2(x,y);
}
void upd1(node* cur,int r,int lo,int hi,int c,long long val){
if(lo>r || hi<r)return;
if(lo==r && hi==r){
if(cur->seg==NULL)cur->seg=new node;
upd2(cur->seg,c,0,offset-1,val);
return;
}
int mid=(lo+hi)/2;
if(mid>=r){
if(cur->l==NULL)cur->l=new node;
upd1(cur->l,r,lo,mid,c,val);
}
else{
if(cur->r==NULL)cur->r=new node;
upd1(cur->r,r,mid+1,hi,c,val);
}
if(cur->seg==NULL)cur->seg=new node;
long long x=0,y=0;
if(cur->l!=NULL)x=(cur->l->seg!=NULL?query2(cur->l->seg,c,c,0,offset-1):0);
if(cur->r!=NULL)y=(cur->r->seg!=NULL?query2(cur->r->seg,c,c,0,offset-1):0);
upd2(cur->seg,c,0,offset-1,gcd2(x,y));
}
long long query1(node* cur,int r1,int r2,int lo,int hi,int c1,int c2){
if(lo>=r1 && hi<=r2){
if(cur->seg==NULL)cur->seg=new node;
return query2(cur->seg,c1,c2,0,offset-1);
}
if(lo>r2 || hi<r1)return 0;
long long x=0,y=0;
int mid=(lo+hi)/2;
if(cur->l!=NULL)x=query1(cur->l,r1,r2,lo,mid,c1,c2);
if(cur->r!=NULL)y=query1(cur->r,r1,r2,mid+1,hi,c1,c2);
return gcd2(x,y);
}
void init(int R, int C) {
root=new node;
}
void update(int P, int Q, long long K) {
upd1(root,P,0,offset-1,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return query1(root,P,U,0,offset-1,Q,V);
}
