#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<iostream>
struct Nd{
long long val=0;
int ch[2]{0,0};
}tree[19800000];
int nx=1;
int L,R;
long long ANS;
int n,m;
int P;
long long VAL;
struct segtree {
int root;
void update(int l,int r,int&node){
if(!node){
node=nx++;
}
if(l==r){
tree[node].val=VAL;
return;
}
int mid=(l+r)>>1;
if(P<=mid){
update(l,mid,tree[node].ch[0]);
}else{
update(mid+1,r,tree[node].ch[1]);
}
tree[node].val=gcd2(tree[tree[node].ch[0]].val,tree[tree[node].ch[1]].val);
}
void update(int p,long long val){
P=p;
update(0,m-1,root);
}
void insert(int l,int r,int&node,int node1,int node2){
if(!node){
node=nx++;
}
tree[node].val=gcd2(tree[node1].val,tree[node2].val);
if(l==r)return;
int mid=(l+r)>>1;
if(P<=mid){
insert(l,mid,tree[node].ch[0],tree[node1].ch[0],tree[node2].ch[0]);
}else{
insert(mid+1,r,tree[node].ch[1],tree[node1].ch[1],tree[node2].ch[1]);
}
}
void insert(int p,int node1,int node2){
P=p;
insert(0,m-1,root,node1,node2);
}
void query(int l,int r,int node){
if(L<=l&r<=R){
ANS=gcd2(ANS,tree[node].val);
return;
}
if(r<L||R<l)return;
int mid=(l+r)>>1;
if(tree[node].ch[0])query(l,mid,tree[node].ch[0]);
if(tree[node].ch[1])query(mid+1,r,tree[node].ch[1]);
}
void query(int l,int r){
L=l,R=r;
query(0,m-1,root);
}
};
struct {
struct {
segtree sst;
int ch[2]{0,0};
}subtree[1000000];
int nxx=1;
void init(int N,int M){
n=N,m=M;
}
int P1,P2;
void update(int l,int r,int&node){
if(!node){
node=++nxx;
}
if(l==r){
subtree[node].sst.update(P2,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.insert(P2,subtree[subtree[node].ch[0]].sst.root,subtree[subtree[node].ch[1]].sst.root);
}
void update(int p1,int p2,long long val){
P1=p1,P2=p2,VAL=val;
int root=1;
update(0,n-1,root);
}
int L1,R1,L2,R2;
void query(int l,int r,int node){
if(L1<=l&&r<=R1){
subtree[node].sst.query(L2,R2);
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,L2=l2,R2=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;
}
