#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#define ll long long
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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;
}
const ll dim=1<<30;
class segment{
public:
struct node{
ll val,left,right;
node(){
val=0;
left=right=-1;
}
};
vector<node> s=vector<node>(1);
node def;
ll upd(ll pos,ll l,ll r,ll p,ll v){
if(l>p || r<p)return s[pos].val;
if(l==r)return s[pos].val=v;
if(s[pos].left==-1){
s[pos].left=s.size();
s.push_back(def);
}
if(s[pos].right==-1){
s[pos].right=s.size();
s.push_back(def);
}
return s[pos].val=gcd2(upd(s[pos].left,l,(l+r)/2,p,v),upd(s[pos].right,(l+r)/2+1,r,p,v));
}
ll query(ll pos,ll l,ll r,ll a,ll b){
if(b<l || r<a)return 0;
if(a<=l && r<=b){
return s[pos].val;
}
ll sx=0,dx=0;
if(s[pos].left!=-1)sx=query(s[pos].left,l,(l+r)/2,a,b);
if(s[pos].right!=-1)dx=query(s[pos].right,(l+r)/2+1,r,a,b);
return gcd2(sx,dx);
}
};
class segofseg{
public:
struct node{
ll left,right;
segment k;
node(){
left=right=-1;
}
};
vector<node> s=vector<node>(1);
node def;
void upd(ll pos,ll l,ll r,ll p,ll q,ll v){
if(l>p || r<p)return ;
if(l==r){
s[pos].k.upd(0,0,dim-1,q,v);
return;
}
ll x=0,y=0;
if(p<=(l+r)/2){
if(s[pos].left==-1){
s[pos].left=s.size();
s.push_back(def);
}
upd(s[pos].left,l,(l+r)/2,p,q,v);
}else{
if(s[pos].right==-1){
s[pos].right=s.size();
s.push_back(def);
}
upd(s[pos].right,(l+r)/2+1,r,p,q,v);
}
if(s[pos].left!=-1)x=s[s[pos].left].k.query(0,0,dim-1,q,q);
if(s[pos].right!=-1)y=s[s[pos].right].k.query(0,0,dim-1,q,q);
s[pos].k.upd(0,0,dim-1,q,gcd2(x,y));
}
ll query(ll pos,ll l,ll r,ll a,ll b,ll x,ll y){
if(b<l || r<a)return 0;
if(a<=l && r<=b){
return s[pos].k.query(0,0,dim-1,x,y);
}
ll sx=0,dx=0;
if(s[pos].left!=-1)sx=query(s[pos].left,l,(l+r)/2,a,b,x,y);
if(s[pos].right!=-1)dx=query(s[pos].right,(l+r)/2+1,r,a,b,x,y);
return gcd2(sx,dx);
}
}tot;
void init(int R, int C) {
}
void update(int P, int Q, long long K){
tot.upd(0,0,dim-1,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return tot.query(0,0,dim-1,P,U,Q,V);
}
