#include "game.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
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 st1{
int n=1;
struct asdf{
int a, b;
ll v;
};
vector<asdf> cad;
void update(int node, int l, int r, int& p, ll v)
{
if(l>p||r<p) return;
if(l==r&&l==p) {cad[node].v=v;return;}
int m=(l+r)/2;
if(m>=p)
{
if(cad[node].a==-1)
{
cad[node].a=cad.size();
cad.push_back({-1,-1,0});
}
update(cad[node].a,l,m,p,v);
}
if(m<p)
{
if(cad[node].b==-1)
{
cad[node].b=cad.size();
cad.push_back({-1,-1,0});
}
update(cad[node].b,m+1,r,p,v);
}
ll temp=0;
if(cad[node].a!=-1) temp=cad[cad[node].a].v;
if(cad[node].b!=-1) temp=gcd2(temp,cad[cad[node].b].v);
cad[node].v=temp;
}
void update(int p, ll v)
{
update(0,1,n,p,v);
}
ll query(int node, int l, int r, int& a, int& b)
{
if(l>b||r<a) return 0;
if(l>=a&&r<=b) return cad[node].v;
if(cad[node].a==-1&&cad[node].b==-1) return 0;
int m=(l+r)/2;
if(cad[node].b==-1) return query(cad[node].a,l,m,a,b);
if(cad[node].a==-1) return query(cad[node].b,m+1,r,a,b);
return gcd2(query(cad[node].a,l,m,a,b),query(cad[node].b,m+1,r,a,b));
}
ll query(int a, int b)
{
return query(0,1,n,a,b);
}
void init()
{
n=1000000000;
cad.reserve(704000);
cad.push_back({-1,-1,0});
}
}nulo;
struct st2{
int n=1;
struct asdf{
int a, b;
st1 v;
};
vector<asdf> cad;
int p1;
void update(int node, int l, int r, int& p, ll v)
{
if(l>p||r<p) return;
if(l==r&&l==p) {cad[node].v.update(p1,v);return;}
int m=(l+r)/2;
if(m>=p)
{
if(cad[node].a==-1)
{
cad[node].a=cad.size();
cad.push_back({-1,-1,nulo});
}
update(cad[node].a,l,m,p,v);
}
if(m<p)
{
if(cad[node].b==-1)
{
cad[node].b=cad.size();
cad.push_back({-1,-1,nulo});
}
update(cad[node].b,m+1,r,p,v);
}
ll temp=0;
if(cad[node].a!=-1) temp=cad[cad[node].a].v.query(p1,p1);
if(cad[node].b!=-1) temp=gcd2(temp,cad[cad[node].b].v.query(p1,p1));
cad[node].v.update(p1,temp);
}
void update(int p,int P, ll v)
{
p1=P;
update(0,1,n,p,v);
}
int c,d;
ll query(int node, int l, int r, int &a, int& b)
{
if(l>b||r<a) return 0;
if(l>=a&&r<=b) return cad[node].v.query(c,d);
if(cad[node].a==-1&&cad[node].b==-1) return 0;
int m=(l+r)/2;
if(cad[node].b==-1) return query(cad[node].a,l,m,a,b);
if(cad[node].a==-1) return query(cad[node].b,m+1,r,a,b);
return gcd2(query(cad[node].a,l,m,a,b),query(cad[node].b,m+1,r,a,b));
}
ll query(int a, int b,int C,int D)
{
c=C;
d=D;
return query(0,1,n,a,b);
}
void init()
{
n=1000000000;
cad.reserve(704000);
cad.push_back({-1,-1,nulo});
}
}asd;
void init(int R, int C) {
nulo.init();
asd.init();
}
void update(int P, int Q, long long K) {
P++;
Q++;
asd.update(P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
P++;
Q++;
U++;
V++;
return asd.query(P,U,Q,V);
}
