#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<<31);
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;
if(cur->l==NULL)cur->l=new node;
if(cur->r==NULL)cur->r=new node;
int mid=(lo+hi)/2;
upd2(cur->l,c,lo,mid,val);
upd2(cur->r,c,mid+1,hi,val);
cur->gcd=gcd2(cur->l->gcd,cur->r->gcd);
}
void upd3(node *cur,node *lcur,node *rcur,int c,int lo,int hi){
if(lo>c || hi<c)return;
cur->gcd=gcd2(lcur->gcd,rcur->gcd);
if(lo==c && hi==c)return;
int mid=(lo+hi)/2;
if(cur->l==NULL)cur->l=new node;
if(cur->r==NULL)cur->r=new node;
if(lcur->l==NULL)lcur->l=new node;
if(lcur->r==NULL)lcur->r=new node;
if(rcur->l==NULL)rcur->l=new node;
if(rcur->r==NULL)rcur->r=new node;
upd3(cur->l,lcur->l,rcur->l,c,lo,mid);
upd3(cur->r,lcur->r,rcur->r,c,mid+1,hi);
}
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;
}
if(cur->l==NULL)cur->l=new node;
if(cur->r==NULL)cur->r=new node;
int mid=(lo+hi)/2;
upd1(cur->l,r,lo,mid,c,val);
upd1(cur->r,r,mid+1,hi,c,val);
if(cur->seg==NULL)cur->seg=new node;
if(cur->l->seg==NULL)cur->l->seg=new node;
if(cur->r->seg==NULL)cur->r->seg=new node;
upd3(cur->seg,cur->l->seg,cur->r->seg,c,0,offset-1);
}
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 -1;
int mid=(lo+hi)/2;
if(cur->l==NULL)cur->l=new node;
if(cur->r==NULL)cur->r=new node;
long long x=query2(cur->l,c1,c2,lo,mid),y=query2(cur->r,c1,c2,mid+1,hi);
if(x==-1)return y;
if(y==-1)return x;
return 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 -1;
int mid=(lo+hi)/2;
if(cur->l==NULL)cur->l=new node;
if(cur->r==NULL)cur->r=new node;
long long x=query1(cur->l,r1,r2,lo,mid,c1,c2),y=query1(cur->r,r1,r2,mid+1,hi,c1,c2);
if(x==-1)return y;
if(y==-1)return x;
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);
}
