#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int r,c;
ll gcd2(ll a,ll b){if(!b)return a;else if(!a)return b;else return gcd2(b,a%b);}
struct node{
node *L = NULL,*R = NULL;
int l,r;
ll val = 0;
node(){}
node(int _l,int _r):l(_l),r(_r){}
void upd(int x,ll v){
if(l == r){val = v;return;}
int mid = (l+r)/2;
node *& tp = (x<=mid?L : R);
if(tp == NULL){
tp = new node(x,x);
tp->val = v;
}else if(tp->l<=x && x<=tp->r)tp->upd(x,v);
else{
//we want to find the ancestor of this node and x
int low = l;
int high = r;
while((x<=mid) == (tp->l <= mid)){
if(x<=mid)high = mid;
else low = mid+1;
mid = (high+low)/2;
}
node * nn = new node(low,high);
//we want to replace tp with nn then attach back the original shit as nn's child
(tp->l<=mid?nn->L : nn->R) = tp;
tp = nn;
nn->upd(x,v);
}
val = gcd2(L==NULL?0:L->val,R == NULL?0:R->val);
}
ll query(int tl,int tr){
if(tl<=l && r<=tr)return val;
if(l > tr || tl > r)return 0;
return gcd2(L?L->query(tl,tr):0 , R?R->query(tl,tr):0);
}
};
struct nodex{
nodex *L = NULL,*R = NULL;
node tree;
ll val = 0;
nodex(){tree = node(1,c);}
}*root;
void upd(nodex *v,int x,int y,int l,int r,ll val){
if(l==r){
v->tree.upd(y,val);
return;
}
else{
int tm =(l+r)/2;
if(x<=tm){
if(v->L == NULL)v->L = new nodex();
upd(v->L,x,y,l,tm,val);
}else{
if(v->R == NULL)v->R = new nodex();
upd(v->R,x,y,tm+1,r,val);
}
}
ll k = gcd2(v->L == NULL?0:v->L->tree.query(y,y) ,
v->R == NULL?0:v->R->tree.query(y,y));
v->tree.upd(y,k);
}
ll query(nodex *v,int xl,int xr,int yl,int yr,int l,int r){
if(xl == l && xr == r){
return v->tree.query(yl,yr);
}
ll res = 0;
int tm = (l+r)/2;
if(xl<=tm && v->L != NULL)res = gcd2(query(v->L,xl,min(tm,xr),yl,yr,l,tm),res);
if(xr> tm && v->R != NULL)res = gcd2(query(v->R,max(xl,tm+1),xr,yl,yr,tm+1,r),res);
return res;
}
void init(int R, int C) {
r=R+1;
c=C+1;
root = new nodex();
}
void update(int P, int Q, ll K) {
P++;
Q++;
upd(root,P,Q,1,r,K);
}
long long calculate(int P, int Q, int U, int V) {
P++;
Q++;
U++;
V++;
return query(root,P,U,Q,V,1,r);
}
