#include "game.h"
#include <cstdio>
typedef long long ll;
#define DBG if(0)
ll gcd2(ll a,ll b){ return b?gcd2(b,a%b):a; }
/*
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 node {
node *lp, *rp;
ll val;
int l,r;
int sing_pos;
node(int a,int b){
l=a; r=b;
lp=rp=0;
val=0;
sing_pos = -1;
}
void insert_val(int pos,ll v){
if(l==r){
val=v;
return;
}
int mid=(l+r)/2;
//printf("insert_val %d,%lld; mid %d\n",pos,v,mid);
if(pos<=mid){
if(!lp) lp=new node(l, mid);
lp->update(pos, v);
} else {
if(!rp) rp=new node(mid+1, r);
rp->update(pos, v);
}
val = 0;
if(lp) val=gcd2(val, lp->val);
if(rp) val=gcd2(val, rp->val);
//printf("my %d~%d : %lld\n",l,r,val);
}
void update(int pos,ll uv){
DBG printf(">>> %lld: i am %d~%d. small-update %d / val %lld\n",ll(this)&0xffff, l,r,pos,uv);
if(lp==0 && rp==0){
if(sing_pos == -1 || sing_pos == pos){
DBG puts("Singular Update");
sing_pos = pos;
val = uv;
return;
} else {
DBG printf("Pushing pre-\n");
insert_val(sing_pos, val);
DBG puts("And...");
insert_val(pos, uv);
}
} else insert_val(pos,uv);
}
ll range(int a,int b){
if(r<a || b<l) return 0;
if(lp==0 && rp==0 && sing_pos!=-1 && a<=sing_pos && sing_pos<=b) return val;
if(a<=l && r<=b){
return val;
}
ll ret=0;
if(lp) ret=gcd2(ret, lp->range(a,b));
if(rp) ret=gcd2(ret, rp->range(a,b));
DBG printf(">>> range %d~%d, get %d~%d : ret %lld\n",l,r,a,b,ret);
return ret;
}
};
int n,m;
struct node2 {
node *p;
int l,r;
node2 *lp, *rp;
node2(int a,int b){
l=a; r=b;
p=new node(0, m-1);
lp=0; rp=0;
}
void update2(int x,int y,ll val){
if(x<l || r<x) return;
DBG printf("\nI am %d~%d. updating %d,%d / val %lld\n", l,r,x,y,val);
if(l==r){
DBG puts("Tada update");
p->update(y,val);
return;
}
int mid=(l+r)/2;
ll yv=0;
if(x<=mid){
if(!lp) lp=new node2(l, mid);
lp->update2(x,y,val);
} else {
if(!rp) rp=new node2(mid+1, r);
rp->update2(x,y,val);
}
yv=gcd2(lp?(lp->p->range(y,y)):0, rp?(rp->p->range(y,y)):0);
DBG printf("%d~%d of %d is %lld\n", l, r, y, yv);
p->update(y, yv);
}
ll range(int a,int b,int x,int y){
if(a<=l && r<=b){
//printf("%d~%d full contain; asking %d~%d\n", l,r,x,y);
return p->range(x,y);
}
if(r<a || b<l) return 0;
ll ret=0;
if(lp) ret=gcd2(ret, lp->range(a,b,x,y));
if(rp) ret=gcd2(ret, rp->range(a,b,x,y));
//printf("xrange %d~%d; ask %d~%d, %d~%d: %lld\n",l,r,a,b,x,y,ret);
return ret;
}
} *root=0;
void init(int R, int C) {
n=R; m=C;
root=new node2(0, n-1);
}
void update(int P, int Q, long long K) {
//putchar(10);
root->update2(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return root->range(P, U, Q, V);
}
