#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
int N,M;
struct Node
{
ll g;
Node *l,*r;
Node(ll _g=0){g=_g;l=r=nullptr;}
void extend(){if(l==nullptr){l=new Node(); r=new Node();}}
void pull(){g=gcd(l->g,r->g);}
};
struct Up
{
Node *root;
Up *l,*r;
Up(){root=new Node();l=r=nullptr;}
void extend(){if(l==nullptr){l=new Up(); r=new Up();}}
};
Up *st;
void update_c_bottom(Node *now,int l,int r,int pos,ll x)
{
if(l==r) now->g=x;
else
{
now->extend();
int m=(l+r)/2;
if(pos<=m) update_c_bottom(now->l,l,m,pos,x);
else update_c_bottom(now->r,m+1,r,pos,x);
now->pull();
}
}
void update_c(Node *now,Node *one,Node *two,int l,int r,int pos)
{
now->g=gcd(one->g,two->g);
if(l<r)
{
int m=(l+r)/2;
now->extend();
one->extend();
two->extend();
if(pos<=m) update_c(now->l,one->l,two->l,l,m,pos);
else update_c(now->r,one->r,two->r,m+1,r,pos);
}
}
void update_r(Up *now,int l,int r,int pos_r,int pos_c,ll x)
{
if(l==r) update_c_bottom(now->root,1,M,pos_c,x);
else
{
now->extend();
int m=(l+r)/2;
if(pos_r<=m) update_r(now->l,l,m,pos_r,pos_c,x);
else update_r(now->r,m+1,r,pos_r,pos_c,x);
update_c(now->root,now->l->root,now->r->root,1,M,pos_c);
}
}
ll query_c(Node *now,int l,int r,int ql,int qr)
{
if(ql>qr||!now) return 0;
if(l==ql&&r==qr) return now->g;
int m=(l+r)/2;
return gcd(query_c(now->l,l,m,ql,min(qr,m)),query_c(now->r,m+1,r,max(ql,m+1),qr));
}
ll query_r(Up *now,int l,int r,int ql,int qr,int cl,int cr)
{
if(ql>qr||!now) return 0;
if(l==ql&&r==qr) return query_c(now->root,1,M,cl,cr);
int m=(l+r)/2;
return gcd(query_r(now->l,l,m,ql,min(qr,m),cl,cr),query_r(now->r,m+1,r,max(ql,m+1),qr,cl,cr));
}
void init(int n,int m)
{
N=n;
M=m;
st=new Up();
}
void update(int r,int c,ll k)
{
r++; c++;
update_r(st,1,N,r,c,k);
}
ll calculate(int p,int q,int u,int v)
{
p++; q++; u++; v++;
return query_r(st,1,N,p,u,q,v);
}
