#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
mt19937 gen(513);
int N,M;
struct Treap;
using twoTreaps=array<Treap*,2>;
struct Treap
{
int p;
ll val;
ll g;
int priority;
twoTreaps kids;
Treap(int np,ll ng){p=np;val=g=ng;priority=gen();kids[0]=kids[1]=nullptr;}
};
void recalc(Treap *me)
{
if(!me) return;
me->g=gcd(gcd(me->kids[0]?me->kids[0]->g:0,me->kids[1]?me->kids[1]->g:0),me->val);
}
twoTreaps tsplit(Treap *me,int lim) //p<=lim
{
if(!me) return {nullptr,nullptr};
if(me->p>lim)
{
auto [one,two]=tsplit(me->kids[0],lim);
me->kids[0]=two;
recalc(me);
return {one,me};
}
else
{
auto [one,two]=tsplit(me->kids[1],lim);
me->kids[1]=one;
recalc(me);
return {me,two};
}
}
Treap* tmerge(Treap *a,Treap *b)
{
if(!a) return b;
if(!b) return a;
if(a->priority<b->priority)
{
a->kids[1]=tmerge(a->kids[1],b);
recalc(a);
return a;
}
else
{
b->kids[0]=tmerge(a,b->kids[0]);
recalc(b);
return b;
}
}
Treap* tupdate(Treap *me,int p,ll g)
{
auto [one,tmp]=tsplit(me,p-1);
auto [two,three]=tsplit(tmp,p);
if(two==nullptr) two=new Treap(p,g);
else two->val=two->g=g;
return tmerge(tmerge(one,two),three);
}
ll tquery(Treap *me,int l,int r)
{
auto [one,tmp]=tsplit(me,l-1);
auto [two,three]=tsplit(tmp,r);
ll g=(two?two->g:0);
tmerge(tmerge(one,two),three);
return g;
}
struct Up
{
Treap *me;
Up *l,*r;
Up(){me=nullptr;l=r=nullptr;}
void extend(){if(!l){l=new Up();r=new Up();}}
};
void update(Up *now,int l,int r,int pos_r,int pos_c,ll g)
{
if(l==r) now->me=tupdate(now->me,pos_c,g);
else
{
now->extend();
int m=(l+r)/2;
if(pos_r<=m) update(now->l,l,m,pos_r,pos_c,g);
else update(now->r,m+1,r,pos_r,pos_c,g);
now->me=tupdate(now->me,pos_c,gcd(tquery(now->l->me,pos_c,pos_c),tquery(now->r->me,pos_c,pos_c)));
}
}
ll query(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 tquery(now->me,cl,cr);
int m=(l+r)/2;
return gcd(query(now->l,l,m,ql,min(qr,m),cl,cr),query(now->r,m+1,r,max(ql,m+1),qr,cl,cr));
}
Up* root=nullptr;
void init(int n,int m)
{
N=n;
M=m;
root=new Up();
}
void update(int r,int c,ll k)
{
update(root,1,N,r+1,c+1,k);
}
ll calculate(int p,int q,int u,int v)
{
return query(root,1,N,p+1,u+1,q+1,v+1);
}
