#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
typedef vector<int> vi;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;
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{
int s,e,m;
ll v;
node *l,*r;
node(int S,int E){
s=S;e=E;m=(s+e)/2;
v=0;l=r=NULL;
}
node(int x,node *n){
int b=(n->e-n->s+1);
if(n->s>x){
e=n->e;
while(e+1-b>x)b<<=1;
s=e+1-b;
l=new node(x,x);r=n;
v=r->v;
}else{
s=n->s;
while(s+b-1<x)b<<=1;
e=s+b-1;
l=n;r=new node(x,x);
v=l->v;
}
m=(s+e)/2;
}
void upd(int x,ll val){
if(s==e){v=val;return;}
if(x<=m){
if(l==NULL)l=new node(x,x);
else if(l->s>x||x>l->e)l=new node(x,l);
l->upd(x,val);
}else{
if(r==NULL)r=new node(x,x);
else if(r->s>x||x>r->e)r=new node(x,r);
r->upd(x,val);
}
v=gcd2((l?l->v:0),(r?r->v:0));
}
ll qry(int x1,int x2){
if(s>=x1&&e<=x2)return v;
if(x2<=m)return (l?l->qry(x1,x2):0);
if(x1>m)return (r?r->qry(x1,x2):0);
return gcd2((l?l->qry(x1,x2):0),(r?r->qry(x1,x2):0));
}
};
struct node2d{
int s,e,m;
node *n;
node2d *l,*r;
node2d(int S,int E){
s=S;e=E;m=(s+e)/2;
n=new node(0,(1<<30)-1);l=r=NULL;
}
void upd(int x,int y,ll val){
if(s==e){
n->upd(y,val);
return;
}
if(x<=m){
if(l==NULL)l=new node2d(s,m);
l->upd(x,y,val);
}else{
if(r==NULL)r=new node2d(m+1,e);
r->upd(x,y,val);
}
ll nv=gcd2((l?l->n->qry(y,y):0),(r?r->n->qry(y,y):0));
n->upd(y,nv);
}
ll qry(int x1,int y1,int x2,int y2){
if(s>=x1&&e<=x2)return (n?n->qry(y1,y2):0);
if(x2<=m)return (l?l->qry(x1,y1,x2,y2):0);
if(x1>m)return (r?r->qry(x1,y1,x2,y2):0);
return gcd2((l?l->qry(x1,y1,x2,y2):0),(r?r->qry(x1,y1,x2,y2):0));
}
}*root=new node2d(0,(1<<30)-1);
void init(int R, int C) {}
void update(int P, int Q, long long K) {
root->upd(P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return root->qry(P,Q,U,V);
}
