#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
inline 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;
}
int R,C;
const int mxn = 3e4+10;
struct SEG2D{
struct node{
ll val;
int pl,pr;
node(){
val = pl = pr = 0;
}
};
struct node2d{
int val;
int pl,pr;
node2d(){
val = pl = pr = 0;
}
};
node seg[mxn*30*30];
node2d seg2[mxn*30];
int ptr = 0,ptr2 = 0;
SEG2D(){}
int newnode(){
ptr++;
assert(ptr<mxn*30*30);
return ptr;
}
int newnode2(){
ptr2++;
assert(ptr2<mxn*30);
return ptr2;
}
int modify(int now,int l,int r,int p,ll v,int pul,int pur){
if(!now)now = newnode();
if(l == r){
if(v >= 0)seg[now].val = v;
else seg[now].val = gcd2(seg[pul].val,seg[pur].val);
return now;
}
int mid = (l+r)>>1;
if(mid>=p)seg[now].pl = modify(seg[now].pl,l,mid,p,v,seg[pul].pl,seg[pur].pl);
else seg[now].pr = modify(seg[now].pr,mid+1,r,p,v,seg[pul].pr,seg[pur].pr);
int ls = seg[now].pl,rs = seg[now].pr;
seg[now].val = gcd2(seg[ls].val,seg[rs].val);
return now;
}
ll getval(int now,int l,int r,int s,int e){
if(!now)return 0ll;
if(l>=s&&e>=r)return seg[now].val;
int mid = (l+r)>>1;
if(mid>=e)return getval(seg[now].pl,l,mid,s,e);
else if(mid<s)return getval(seg[now].pr,mid+1,r,s,e);
else return gcd2(getval(seg[now].pl,l,mid,s,e),getval(seg[now].pr,mid+1,r,s,e));
}
int modify2(int now,int l,int r,int row,int col,ll v){
if(!now)now = newnode2();
if(l == r){
seg2[now].val = modify(seg2[now].val,0,C,col,v,0,0);
//cerr<<"SEG2D:"<<' '<<l<<' '<<r<<' '<<seg[seg2[now].val].val<<endl;
return now;
}
int mid = (l+r)>>1;
if(mid>=row)seg2[now].pl = modify2(seg2[now].pl,l,mid,row,col,v);
else seg2[now].pr = modify2(seg2[now].pr,mid+1,r,row,col,v);
seg2[now].val = modify(seg2[now].val,0,C,col,-1,seg2[seg2[now].pl].val,seg2[seg2[now].pr].val);
//cerr<<"SEG2D:"<<' '<<l<<' '<<r<<' '<<seg[seg2[now].val].val<<endl;
return now;
}
ll getval2(int now,int l,int r,int sr,int sc,int er,int ec){
if(!now)return 0ll;
if(l>=sr&&er>=r){
//cerr<<"GETVAL: "<<l<<' '<<r<<' '<<getval(seg2[now].val,0,C,sc,ec)<<endl;
return getval(seg2[now].val,0,C,sc,ec);
}
int mid = (l+r)>>1;
if(mid>=er)return getval2(seg2[now].pl,l,mid,sr,sc,er,ec);
else if(mid<sr)return getval2(seg2[now].pr,mid+1,r,sr,sc,er,ec);
else return gcd2(getval2(seg2[now].pl,l,mid,sr,sc,er,ec),getval2(seg2[now].pr,mid+1,r,sr,sc,er,ec));
}
};
SEG2D seg;
int rt;
void init(int RR, int CC) {
R = RR,C = CC;
//cerr<<"INIT!"<<" "<<R<<' '<<C<<endl;
rt = seg.newnode2();
//cerr<<"INIT!"<<endl;
}
void update(int P, int Q, long long K) {
//cerr<<"UPDATE: "<<P<<' '<<Q<<' '<<K<<endl;
rt = seg.modify2(rt,0,R,P,Q,K);
//cerr<<"UPDATE DONE!"<<endl;
}
long long calculate(int P, int Q, int U, int V) {
//cerr<<"CALC: "<<P<<' '<<Q<<' '<<U<<' '<<V<<endl;
return seg.getval2(rt,0,R,P,Q,U,V);
}
