// interaction header
#include "game.h"
typedef long long ll;
struct ii
{
int first, second;
ii(int _a = 0, int _b = 0) : first(_a), second(_b) {}
};
inline ll gcd(ll x, ll y)
{
if (!x)
return y;
if (!y)
return x;
if (x < 0)
x = -x;
if (y < 0)
y = -y;
ll t = __builtin_ctzll(x | y);
x >>= __builtin_ctzll(x);
do
{
y >>= __builtin_ctzll(y);
if (x > y)
{
ll tmp = x;
x = y;
y = tmp;
}
y -= x;
} while (y);
return x << t;
}
inline ll func(ll X, ll Y) { return gcd(X, Y); }
// 2D Dynamic Query Tree from errorgorn
// find lca of 2 nodes
ii lca(int l, int r, int pos)
{
if (pos < l)
{
int p = 32 - __builtin_clz(pos ^ l);
int lp = (pos >> p) << p;
return ii(lp, lp + (1 << p) - 1);
}
if (r < pos)
{
int p = 32 - __builtin_clz(r ^ pos);
int lp = (l >> p) << p;
return ii(lp, lp + (1 << p) - 1);
}
return ii(pos, 0);
}
struct node
{
int s, e, m;
ll val = 0;
node *l = nullptr, *r = nullptr;
node(int _s, int _e)
{
s = _s, e = _e, m = (s + e) >> 1;
}
bool inside(int i)
{
return s <= i && i <= e;
}
void update(int i, ll j)
{
if (s == e)
val = j;
else
{
if (i <= m)
{
if (l == nullptr)
l = new node(i, i);
else if (!l->inside(i))
{
node *temp = l;
ii child = lca(l->s, l->e, i);
l = new node(child.first, child.second);
if (temp->e <= l->m)
l->l = temp;
else
l->r = temp;
}
l->update(i, j);
}
else
{
if (r == nullptr)
r = new node(i, i);
else if (!r->inside(i))
{
node *temp = r;
ii child = lca(r->s, r->e, i);
r = new node(child.first, child.second);
if (temp->e <= r->m)
r->l = temp;
else
r->r = temp;
}
r->update(i, j);
}
val = func((l == nullptr) ? 0 : l->val, (r == nullptr) ? 0 : r->val);
}
}
ll query(int i, int j)
{
if (i <= s && e <= j)
return val;
else if (j <= m)
return (l == nullptr) ? 0 : l->query(i, j);
else if (m < i)
return (r == nullptr) ? 0 : r->query(i, j);
else
return func((l == nullptr) ? 0 : l->query(i, m), (r == nullptr) ? 0 : r->query(m + 1, j));
}
node *clone()
{
node *res = new node(s, e);
res->val = val;
res->l = (l == nullptr) ? nullptr : l->clone();
res->r = (r == nullptr) ? nullptr : r->clone();
return res;
}
};
struct node2d
{
int s, e, m;
node *val = new node(0, (1 << 30) - 1);
node2d *l = nullptr, *r = nullptr;
node2d(int _s, int _e)
{
s = _s, e = _e, m = s + e >> 1;
}
bool inside(int i)
{
return s <= i && i <= e;
}
void update(int i, int j, ll k)
{
if (s == e)
val->update(j, k);
else
{
if (i <= m)
{
if (l == nullptr)
l = new node2d(i, i);
else if (!l->inside(i))
{
node2d *temp = l;
ii child = lca(l->s, l->e, i);
l = new node2d(child.first, child.second);
if (temp->e <= l->m)
l->l = temp;
else
l->r = temp;
l->val = temp->val->clone();
}
l->update(i, j, k);
}
else
{
if (r == nullptr)
r = new node2d(i, i);
else if (!r->inside(i))
{
node2d *temp = r;
ii child = lca(r->s, r->e, i);
r = new node2d(child.first, child.second);
if (temp->e <= r->m)
r->l = temp;
else
r->r = temp;
r->val = temp->val->clone();
}
r->update(i, j, k);
}
val->update(j, func((l == nullptr) ? 0 : l->val->query(j, j), (r == nullptr) ? 0 : r->val->query(j, j)));
}
}
ll query(int i, int j, int i2, int j2)
{
if (i <= s && e <= j)
return val->query(i2, j2);
else if (j <= m)
return (l == nullptr) ? 0 : l->query(i, j, i2, j2);
else if (m < i)
return (r == nullptr) ? 0 : r->query(i, j, i2, j2);
else
return func((l == nullptr) ? 0 : l->query(i, m, i2, j2), (r == nullptr) ? 0 : r->query(m + 1, j, i2, j2));
}
} *root = new node2d(0, (1 << 30) - 1);
void init(int R, int C) {}
void update(int P, int Q, ll K) { root->update(P, Q, K); }
ll calculate(int P, int Q, int U, int V) { return root->query(P, U, Q, V); }
