#include "game.h"
#include<bits/stdc++.h>
#define int long long
#define I signed
int gcd2(int X, int Y) {
int tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
#define TN 3<<18
namespace TREAP{
std::mt19937 rng(std::random_device{}());
int RR,lc[TN],rc[TN],key[TN],ind[TN],ccnt;
int val[TN],sub[TN];
int newnode(int v,int i){
ind[++ccnt]=i;
key[ccnt]=rng();
val[ccnt]=sub[ccnt]=v;
return ccnt;
}
void maint(int n){
sub[n]=std::__gcd(std::__gcd(sub[lc[n]],sub[rc[n]]),val[n]);
}
int merge(int a,int b){
if(!a||!b)
return a+b;
if(key[a]<key[b]) {
rc[a]=merge(rc[a],b);
maint(a); return a;
}
lc[b]=merge(a,lc[b]);
maint(b); return b;
}
void split(int a,int p1,int p2,int&x,int&y){
if(!a) return void(x=y=0);
if(ind[a]>p1||ind[a]==p1&&val[a]>p2)
y=a,split(lc[a],p1,p2,x,lc[a]);
else x=a,split(rc[a],p1,p2,rc[a],y);
maint(a);
}
}
namespace SEG{
int ccnt=0,lc[TN],rc[TN],rt[TN],rtt=0;
void ins(int &i,int p,int q,int x,int l,int r){
if(!i) i=++ccnt;
int A,B,C=TREAP::newnode(x,q);
TREAP::split(rt[i],q,x,A,B);
rt[i]=TREAP::merge(A,TREAP::merge(C,B));
if(l==r) return;
if(l+r>>1<p)
ins(rc[i],p,q,x,l+r+2>>1,r);
else ins(lc[i],p,q,x,l,l+r>>1);
}
void del(int i,int p,int q,int x,int l,int r){
int A,B,C;
TREAP::split(rt[i],q,x,B,C);
TREAP::split(B,q,x-1,A,B);
B=TREAP::merge(TREAP::lc[B],TREAP::rc[B]);
rt[i]=TREAP::merge(A,TREAP::merge(B,C));
if(l==r)return;
if(l+r>>1<p)
del(rc[i],p,q,x,l+r+2>>1,r);
else del(lc[i],p,q,x,l,l+r>>1);
}
int query(int i,int ll,int rr,int ql,int qr,int l,int r){
if(!i) return 0;
if(ll>r||l>rr)
return 0;
if(ll<=l&&r<=rr){
int A,B,C,D;
TREAP::split(rt[i],qr,1e18,B,C);
TREAP::split(B,ql,0,A,B);
D=TREAP::sub[B];
rt[i]=TREAP::merge(A,TREAP::merge(B,C));
return D;
}
return std::__gcd(query(i*2,ll,rr,ql,qr,l,l+r>>1),query(i*2+1,ll,rr,ql,qr,l+r+2>>1,r));
}
}
std::map<int,std::map<int,int>>mp;
void init(I R, I C) {
TREAP::RR=R;
}
void update(I P, I Q, int K) {
if(!K) return;
if(mp[P][Q])
SEG::del(SEG::rtt,P,Q,K,0,TREAP::RR-1);
SEG::ins(SEG::rtt,P,Q,mp[P][Q]=K,0,TREAP::RR-1);
}
int calculate(I P, I Q, I U, I V) {
return SEG::query(SEG::rtt,P,U,Q,V,0,TREAP::RR-1);
}
#undef int
#undef I
