#include "game.h"
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;
}
#include<bits/stdc++.h>
using namespace std;
int L,R;
long long ANS;
int n,m;
int P;
long long VAL;
struct treap {
struct Node{
long long val=0,all=0;
int ind=0,pri=rand(),l,r;
Node*lc=0,*rc=0;
Node(){}
Node(long long VAL,int IND){
val=all=VAL;
ind=l=r=IND;
}
};
using pnode=Node*;
pnode root=new Node(0,0);
#define cur tree[node]
void query(pnode p){
if(!p)return;
if(p->r<L||R<p->l)return;
if(L<=p->l&&p->r<=R){
ANS=gcd2(ANS,p->all);
return;
}
if(L<=p->ind&&p->ind<=R){
ANS=gcd2(ANS,p->val);
}
if(L<=p->ind)query(p->lc);
if(p->ind<=R)query(p->rc);
}
void query(){query(root);};
long long pquery(pnode p){
if(!p)return 0;
if(p->ind==P)return p->val;
if(P<p->ind)return pquery(p->lc);
return pquery(p->rc);
}
long long pquery(){return pquery(root);}
int getl(pnode p){
if(p)return p->l;
return 2000000000;
}
int getr(pnode p){
if(p)return p->r;
return -1;
}
int getall(pnode p){
if(p)return p->all;
return 0;
}
void upd(pnode p){
if(!p)return;
p->all=gcd2(p->all,gcd2(getall(p->lc),getall(p->rc)));
p->l=min(p->ind,getl(p->lc));
p->r=max(p->ind,getr(p->rc));
}
void split(pnode p,pnode&l,pnode&r,int ind){
if(!p){
l=r=0;
return;
}
if(p->ind<ind){
split(p->rc,p->rc,r,ind);
l=p;
}else{
split(p->lc,l,p->lc,ind);
r=p;
}
upd(p);
}
void merge(pnode&p,pnode l,pnode r){
if(!l){
p=r;
return;
}
if(!r){
p=l;
return;
}
if(r->pri<l->pri){
merge(l->rc,l->rc,r);
p=l;
}else{
merge(r->lc,l,r->lc);
p=r;
}
upd(p);
}
void update(long long val){
pnode t1,t2,t3;
t1=t2=t3=0;
split(root,t1,t2,P);
split(t2,t2,t3,P+1);
if(t2){
t2->val=t2->all=val;
}else{
t2=new Node(val,P);
}
merge(root,t1,t2);
merge(root,root,t3);
}
};
struct {
struct {
treap sst;
int ch[2]{0,0};
}subtree[1000000];
int nxx=1;
void init(int N,int M){
n=N,m=M;
}
int P1;
void update(int l,int r,int&node){
if(!node){
node=++nxx;
}
if(l==r){
subtree[node].sst.update(VAL);
return;
}
int mid=(l+r)>>1;
if(P1<=mid){
update(l,mid,subtree[node].ch[0]);
}else{
update(mid+1,r,subtree[node].ch[1]);
}
subtree[node].sst.update(gcd2(subtree[subtree[node].ch[0]].sst.pquery(),subtree[subtree[node].ch[1]].sst.pquery()));
}
void update(int p1,int p2,long long val){
P1=p1,P=p2,VAL=val;
L=R=P;
int root=1;
update(0,n-1,root);
}
int L1,R1;
void query(int l,int r,int node){
if(L1<=l&&r<=R1){
subtree[node].sst.query();
return;
}
if(r<L1||R1<l)return;
int mid=(l+r)>>1;
if(subtree[node].ch[0])query(l,mid,subtree[node].ch[0]);
if(subtree[node].ch[1])query(mid+1,r,subtree[node].ch[1]);
}
long long query(int l1,int r1,int l2,int r2){
L1=l1,R1=r1,L=l2,R=r2;
ANS=0;
query(0,n-1,1);
return ANS;
}
}st;
void init(int R, int C) {
st.init(R,C);
}
void update(int P, int Q, long long K) {
st.update(P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
long long val=st.query(P,U,Q,V);
return val;
}
