#include "game.h"
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll gcd2(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
long long mxN = 1<<30;
struct seg1d{
int lb, rb;
ll val;
seg1d *l, *r;
seg1d () : l(NULL), r(NULL), val(0) {}
inline void init(int lx, int rx){
lb = lx, rb = rx;
}
inline void exl(){
int mid = (lb+rb)>>1;
l = new seg1d;
l->init(lb,mid);
}
inline void exr(){
int mid = (lb+rb)>>1;
r = new seg1d;
r->init(mid+1,rb);
}
ll getGCD(int llb, int rrb){
if(llb > rb || rrb < lb)return 0;
if(llb <= lb && rrb >= rb)return val;
if(l == NULL && r == NULL)return 0;
if(l == NULL)return r->getGCD(llb,rrb);
if(r == NULL)return l->getGCD(llb,rrb);
return gcd2(r->getGCD(llb,rrb),l->getGCD(llb,rrb));
}
void ch(int x, ll va){
if(rb < x || lb > x)return;
if(rb == x && lb == x){
val = va;
return;
}
int mid = (lb+rb)>>1;
if(mid >= x){
if(l == NULL)exl();
l->ch(x,va);
if(r == NULL)val = l->val;
else val = gcd2(l->val,r->val);
}
else{
if(r == NULL)exr();
r->ch(x,va);
if(l == NULL)val = r->val;
else val = gcd2(l->val,r->val);
}
}
void chno(seg1d *a, seg1d *b, int x){
if(rb < x || lb > x)return;
int mid = (lb+rb)>>1;
if(mid >= x){
if(a == NULL){
val = b->val;
if(rb == lb)return;
if(l == NULL)exl();
l->chno(a,b->l,x);
return;
}
if(b == NULL){
val = a->val;
if(rb == lb)return;
if(l == NULL)exl();
l->chno(a->l,b,x);
return;
}
val = gcd2(a->val,b->val);
if(rb == lb)return;
if(l == NULL)exl();
l->chno(a->l,b->l,x);
}
else{
if(a == NULL){
val = b->val;
if(rb == lb)return;
if(r == NULL)exr();
r->chno(a,b->r,x);
return;
}
if(b == NULL){
val = a->val;
if(rb == lb)return;
if(r == NULL)exr();
r->chno(a->r,b,x);
return;
}
val = gcd2(a->val,b->val);
if(rb == lb)return;
if(r == NULL)exr();
r->chno(a->r,b->r,x);
}
}
};
struct seg2d{
int lb, rb;
seg2d *l, *r;
seg1d *c;
seg2d () : l(NULL), r(NULL), c(NULL) {}
inline void init(int lx, int rx){
lb = lx, rb = rx;
}
inline void exl(){
int mid = (lb+rb)>>1;
l = new seg2d;
l->init(lb,mid);
}
inline void exr(){
int mid = (lb+rb)>>1;
r = new seg2d;
r->init(mid+1,rb);
}
inline void exc(){
c = new seg1d;
c->init(0, mxN);
}
ll getGCD(int llb, int rrb, int uub, int ddb){
if(llb > rb || rrb < lb)return 0;
if(llb <= lb && rrb >= rb){
if(c == NULL)return 0;
return c->getGCD(uub,ddb);
}
if((l == NULL && r == NULL) || c == NULL)return 0;
if(r == NULL)return l->getGCD(llb,rrb,uub,ddb);
if(l == NULL)return r->getGCD(llb,rrb,uub,ddb);
return gcd2(r->getGCD(llb,rrb,uub,ddb),l->getGCD(llb,rrb,uub,ddb));
}
void ch(int x, int y, ll val){
if(rb < x || lb > x)return;
if(rb == x && lb == x){if(c == NULL)exc();c->ch(y,val);return;}
int mid = (rb+lb)>>1;
if(mid >= x){
if(l == NULL)exl();
if(c == NULL)exc();
l->ch(x,y,val);
if(r == NULL){
exr();
}
c->chno(l->c,r->c,y);
}
else{
if(r == NULL)exr();
if(c == NULL)exc();
r->ch(x,y,val);
if(l == NULL){
exl();
}
c->chno(l->c,r->c,y);
}
}
};
seg2d root;
void init(int R, int C) {
root.init(0,mxN);
}
void update(int P, int Q, long long K) {
root.ch(P+1,Q+1,K);
}
long long calculate(int P, int Q, int U, int V) {
return root.getGCD(P+1,U+1,Q+1,V+1);
}
