#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+5;
struct Node
{
int lson;
int rson;
int gcd;
};
Node emptyNode={0,0,0};
class AINT
{
public:
int 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;
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;
}
} nush[2005];
struct Node_baban
{
AINT a;
int lson;
int rson;
};
Node_baban emptyNode_baban={{0,{emptyNode}},0,0};
class AINT_baban
{
public:
int sz;
vector<Node_baban> aint;
void init()
{
sz=0;
aint.clear();
aint.push_back(emptyNode_baban);
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);
return;
}
int mid;
mid=(l+r)/2;
aint[val].a.update(0,lim,0,y,k);
if (x<=mid)
{
if (aint[val].lson==0)
{
sz++;
aint[val].lson=sz;
aint.push_back(emptyNode_baban);
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.push_back(emptyNode_baban);
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();
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);
//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);
}
