#include<bits/stdc++.h>
#include "game.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int range_rng(int l, int r)
{
return uniform_int_distribution<int>(l,r)(rng);
}
const int lim=1e9;
map<signed,signed> mp;
signed cnt;
struct Node
{
signed lson;
signed rson;
int gcd;
};
Node emptyNode= {0,0,0};
class AINT_aux
{
public:
signed sz;
vector<Node> aint;
void init()///de preferat apeleaza asta
{
sz=0;
aint.clear();
aint.push_back(emptyNode);
}
void update(int l, int r, int val, int poz, int x)
{
if (l==r)
{
aint[val].gcd=x;///asta e aintu auxiliar
return;
}
int mid;
mid=(l+r)/2;
if (poz<=mid)
{
if (aint[val].lson==0)
{
sz++;
aint[val].lson=sz;
aint.push_back(emptyNode); //aint[sz]=emptyNode;
}
update(l,mid,aint[val].lson,poz,x);
}
else
{
if (aint[val].rson==0)
{
sz++;
aint[val].rson=sz;
aint.push_back(emptyNode); //aint[sz]=emptyNode;
}
update(mid+1,r,aint[val].rson,poz,x);
}
aint[val].gcd=0;
if (aint[val].lson!=0)
aint[val].gcd=__gcd(aint[val].gcd,aint[aint[val].lson].gcd);
if (aint[val].rson!=0)
aint[val].gcd=__gcd(aint[val].gcd,aint[aint[val].rson].gcd);
}
int query(int l, int r, int val, int qa, int qb)
{
if (qa<=l && r<=qb)
{
return aint[val].gcd;
}
int mid,ans;
mid=(l+r)/2;
ans=0;
if (qa<=mid)
{
if (aint[val].lson!=0)
ans=__gcd(ans,query(l,mid,aint[val].lson,qa,qb));
}
if (qb>mid)
{
if (aint[val].rson!=0)
ans=__gcd(ans,query(mid+1,r,aint[val].rson,qa,qb));
}
return ans;
}
} ainta[23000];
class AINT
{
public:
signed sz;
vector<Node> aint;
void init()///de preferat apeleaza asta
{
sz=0;
aint.clear();
aint.push_back(emptyNode);
}
void update(int l, int r, int val, int poz, int x, int l1, int l2)
{
if (l==r)
{
aint[val].gcd=ainta[mp[poz]].query(0,lim,0,l1,l2);
return;
}
int mid;
mid=(l+r)/2;
if (poz<=mid)
{
if (aint[val].lson==0)
{
sz++;
aint[val].lson=sz;
aint.push_back(emptyNode); //aint[sz]=emptyNode;
}
update(l,mid,aint[val].lson,poz,x,l1,l2);
}
else
{
if (aint[val].rson==0)
{
sz++;
aint[val].rson=sz;
aint.push_back(emptyNode); //aint[sz]=emptyNode;
}
update(mid+1,r,aint[val].rson,poz,x,l1,l2);
}
aint[val].gcd=0;
if (aint[val].lson!=0)
aint[val].gcd=__gcd(aint[val].gcd,aint[aint[val].lson].gcd);
if (aint[val].rson!=0)
aint[val].gcd=__gcd(aint[val].gcd,aint[aint[val].rson].gcd);
}
int query(int l, int r, int val, int qa, int qb)
{
if (qa<=l && r<=qb)
{
return aint[val].gcd;
}
int mid,ans;
mid=(l+r)/2;
ans=0;
if (qa<=mid)
{
if (aint[val].lson!=0)
ans=__gcd(ans,query(l,mid,aint[val].lson,qa,qb));
}
if (qb>mid)
{
if (aint[val].rson!=0)
ans=__gcd(ans,query(mid+1,r,aint[val].rson,qa,qb));
}
return ans;
}
};
struct Node_baban
{
signed lson;
signed rson;
AINT a;
};
Node_baban emptyNode_baban= {0,0,{0,{emptyNode}}};
class AINT_baban
{
public:
signed sz;
Node_baban aint[200000];
void init()
{
sz=0;
//aint.clear();
aint[0]=emptyNode_baban;//aint.push_back(emptyNode_baban);
aint[0].a.init();//aint.back().a.init();
}
void update(int l, int r, int val, int x, int y, int k)
{
if (l==r)
{
aint[val].a.update(0,lim,0,y,k,l,r);
return;
}
int mid;
mid=(l+r)/2;
aint[val].a.update(0,lim,0,y,k,l,r);
if (x<=mid)
{
if (aint[val].lson==0)
{
sz++;
aint[val].lson=sz;
aint[sz]=emptyNode_baban;//aint.push_back(emptyNode_baban);
aint[sz].a.init();//aint.back().a.init();
}
update(l,mid,aint[val].lson,x,y,k);
}
else
{
if (aint[val].rson==0)
{
sz++;
aint[val].rson=sz;
aint[sz]=emptyNode_baban;//aint.push_back(emptyNode_baban);
aint[sz].a.init();//aint.back().a.init();
}
update(mid+1,r,aint[val].rson,x,y,k);
}
}
int query(int l, int r, int val, int x1, int x2, int y1, int y2)
{
if (x1<=l && r<=x2)
{
return aint[val].a.query(0,lim,0,y1,y2);
}
int mid,ans;
mid=(l+r)/2;
ans=0;
if (x1<=mid)
{
if (aint[val].lson!=0)
ans=__gcd(ans,query(l,mid,aint[val].lson,x1,x2,y1,y2));
}
if (x2>mid)
{
if (aint[val].rson!=0)
ans=__gcd(ans,query(mid+1,r,aint[val].rson,x1,x2,y1,y2));
}
return ans;
}
} hurkacz;
void init(signed R, signed C)
{
hurkacz.init();
cnt=0;
/*
int i;
for (i=0;i<R;i++)
nush[i].init();
*/
}
void update(signed P, signed Q, long long K)
{
//nush[P].update(0,lim,0,Q,K);
if (mp.find(Q)==mp.end())
{
mp[Q]=++cnt;
ainta[mp[Q]].init();
}
ainta[mp[Q]].update(0,lim,0,P,K);
hurkacz.update(0,lim,0,P,Q,K);
}
long long calculate(signed P, signed Q, signed U, signed V)
{
/*
int ans,i;
ans=0;
for (i=P;i<=U;i++)
{
ans=__gcd(ans,nush[i].query(0,lim,0,Q,V));
}
return ans;
*/
return hurkacz.query(0,lim,0,P,U,Q,V);
}
