// M
#include<bits/stdc++.h>
#include "game.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
typedef long long ll;
const int N = 22005, TF = 400, MXS = N * 4, NS = N * 15;
int n, m, k, segk;
map < pair < int , int > , ll > MP, TMp;
vector < pair < int , int > > V[N], VC[MXS];
vector < int > UX, VID[MXS];
ll G[NS * 2];
inline void ModifySeg(int i, ll val)
{
G[i += NS] = val;
for (; i; i >>= 1)
G[i >> 1] = __gcd(G[i], G[i ^ 1]);
}
inline ll GetSeg(int l, int r)
{
ll g = 0;
for (l += NS, r += NS; l < r; l >>= 1, r >>= 1)
{
if (l & 1) g = __gcd(g, G[l ++]);
if (r & 1) g = __gcd(g, G[-- r]);
}
return g;
}
void Build(int id = 1, int l = 0, int r = k)
{
VC[id].clear();
VID[id].clear();
if (r - l < 2)
sort(V[l].begin(), V[l].end()), VC[id] = V[l];
else
{
Build(lc, l, md);
Build(rc, md, r);
merge(VC[lc].begin(), VC[lc].end(), VC[rc].begin(), VC[rc].end(), back_inserter(VC[id]));
}
for (int i = 0; i < (int)VC[id].size(); i ++)
{
ModifySeg(segk, MP[make_pair(VC[id][i].second, VC[id][i].first)]);
VID[id].push_back(segk ++);
}
}
inline void Relax()
{
segk = 0;
memset(G, 0, sizeof(G));
UX.clear();
for (auto X : TMp)
MP[X.first] = X.second;
TMp.clear();
for (auto e : MP)
UX.push_back(e.first.first);
UX.resize(unique(UX.begin(), UX.end()) - UX.begin());
k = (int)UX.size();
for (int i = 0; i <= k; i ++)
V[i].clear();
int ptr = 0;
for (auto e : MP)
{
while (UX[ptr] < e.first.first)
ptr ++;
V[ptr].push_back(make_pair(e.first.second, e.first.first));
}
Build();
assert(segk < NS);
}
void Update(int i, int c, ll val, int id = 1, int l = 0, int r = k)
{
int lb = (int)(lower_bound(VC[id].begin(), VC[id].end(), make_pair(c, UX[i])) - VC[id].begin());
ModifySeg(VID[id][lb], val);
if (r - l < 2)
return ;
if (i < md)
Update(i, c, val, lc, l, md);
else
Update(i, c, val, rc, md, r);
}
void init(int _n, int _m)
{
n = _n; m = _m;
Relax();
}
void update(int r, int c, ll val)
{
if (MP.count({r, c}))
{
r = lower_bound(UX.begin(), UX.end(), r) - UX.begin();
Update(r, c, val);
MP[make_pair(UX[r], c)] = val;
}
else
{
TMp[make_pair(r, c)] = val;
if ((int)TMp.size() >= TF)
Relax();
}
}
ll Get(int le, int ri, int lq, int rq, int id = 1, int l = 0, int r = k)
{
if (ri <= l || r <= le)
return 0LL;
if (le <= l && r <= ri)
{
int lb = (int)(lower_bound(VC[id].begin(), VC[id].end(), make_pair(lq, -1)) - VC[id].begin());
int ub = (int)(lower_bound(VC[id].begin(), VC[id].end(), make_pair(rq, -1)) - VC[id].begin());
if (lb < ub)
return GetSeg(VID[id][lb], VID[id][ub - 1] + 1);
}
return __gcd(Get(le, ri, lq, rq, lc, l, md), Get(le, ri, lq, rq, rc, md, r));
}
inline ll Query(int a, int b, int c, int d)
{
c ++; d ++;
a = lower_bound(UX.begin(), UX.end(), a) - UX.begin();
c = lower_bound(UX.begin(), UX.end(), c) - UX.begin();
return Get(a, c, b, d);
}
ll calculate(int a, int b, int c, int d)
{
ll g = Query(a, b, c, d);
for (auto e : TMp)
if (e.first.first >= a && e.first.first <= c && e.first.second >= b && e.first.second <= d)
g = __gcd(g, e.second);
return g;
}
