#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int inf=1e9+5,M=8e5;
mt19937 rng(time(0));
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 Treap{
int nc,lc[M],rc[M],pr[M];
ll a[M],sum[M];
pair<int,int>ind[M];
Treap(){for(int i=0;i<M;i++)pr[i]=rng();}
void pull(int c){sum[c]=gcd2(gcd2(sum[lc[c]],sum[rc[c]]),a[c]);}
int Merge(int c1,int c2){
if(!c1){pull(c2);return c2;}
if(!c2){pull(c1);return c1;}
int c=pr[c1]<pr[c2]?c1:c2;
if(pr[c1]<pr[c2])rc[c1]=Merge(rc[c1],c2);
else lc[c2]=Merge(c1,lc[c2]);
pull(c);
return c;
}
void Split(int c,int &c1,int &c2,pair<int,int>k){
if(!c){c1=c2=0;return;}
if(ind[c]>k){c2=c;Split(lc[c],c1,lc[c2],k);}
else{c1=c;Split(rc[c],rc[c1],c2,k);}
pull(c);
}
void Insert(int &c,int qx,int qy,ll qval){
++nc;
ind[nc]={qy,qx};
a[nc]=sum[nc]=qval;
int rt1=0,rt2=0;
Split(c,rt1,rt2,ind[nc]);
c=Merge(rt1,nc);
c=Merge(c,rt2);
}
void Erase(int &c,int qx,int qy){
int rt1=0,rt2=0,rt3=0;
Split(c,rt1,rt2,{qy,qx-1});
Split(rt2,rt2,rt3,{qy,qx});
c=Merge(rt1,rt3);
}
ll Get(int &c,int ql,int qr){
int rt1=0,rt2=0,rt3=0;
Split(c,rt1,rt2,{ql-1,inf});
Split(rt2,rt2,rt3,{qr,inf});
ll res=sum[rt2];
c=Merge(rt1,rt2);
c=Merge(c,rt3);
return res;
}
}treap;
int nc,Root,root[M],lc[M],rc[M];
void Update(int &c,int ss,int se,int qx,int qy,ll qval){
if(!c)c=++nc;
treap.Erase(root[c],qx,qy);
treap.Insert(root[c],qx,qy,qval);
if(ss==se)return;
int mid=ss+se>>1;
if(qx<=mid)Update(lc[c],ss,mid,qx,qy,qval);
else Update(rc[c],mid+1,se,qx,qy,qval);
}
ll Get(int c,int ss,int se,int qs,int qe,int ql,int qr){
if(!c||qs>qe||qe<ss||se<qs)return 0;
if(qs<=ss&&se<=qe)return treap.Get(root[c],ql,qr);
int mid=ss+se>>1;
if(qe<mid+1)return Get(lc[c],ss,mid,qs,qe,ql,qr);
if(mid<qs)return Get(rc[c],mid+1,se,qs,qe,ql,qr);
return gcd2(Get(lc[c],ss,mid,qs,qe,ql,qr),Get(rc[c],mid+1,se,qs,qe,ql,qr));
}
void init(int R, int C){}
void update(int P, int Q, long long K) {
Update(Root,0,inf,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return Get(Root,0,inf,P,U,Q,V);
}
