#include "game.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
struct node0 {
ll x;
int l, r;
} pool0[10000000];
struct node1 {
int x;
int l, r;
} pool1[10000000];
int new_node0(){static int nxt=1; return nxt++;}
int new_node1(){static int nxt=1; return nxt++;}
void up0(int p, ll x, int t, int b=0, int e=1e9)
{
#define t (pool0+t)
if (e-b == 1) {
t->x = x;
return;
}
if (p < (b+e)/2) {
if (!t->l) t->l = new_node0();
up0(p, x, t->l, b, (b+e)/2);
} else {
if (!t->r) t->r = new_node0();
up0(p, x, t->r, (b+e)/2, e);
}
t->x = __gcd(t->l? pool0[t->l].x: 0, t->r? pool0[t->r].x: 0);
#undef t
}
void merge0(int p, int l, int r, int t, int b=0, int e=1e9)
{
#define t (pool0+t)
t->x = __gcd(l? pool0[l].x: 0, r? pool0[r].x: 0);
if (e-b == 1)
return;
if (p < (b+e)/2) {
if (!t->l) t->l = new_node0();
merge0(p, l? pool0[l].l: 0, r? pool0[r].l: 0, t->l, b, (b+e)/2);
} else {
if (!t->r) t->r = new_node0();
merge0(p, l? pool0[l].r: 0, r? pool0[r].r: 0, t->r, (b+e)/2, e);
}
#undef t
}
ll get0(int l, int r, int t, int b=0, int e=1e9)
{
#define t (pool0+t)
if (r <= b || e <= l || !t)
return 0;
if (l <= b && e <= r)
return t->x;
return __gcd(get0(l, r, t->l, b, (b+e)/2),
get0(l, r, t->r, (b+e)/2, e));
#undef t
}
int seg0_cpy(int t)
{
if (!t)
return 0;
#define t (pool0+t)
int ans = new_node0();
pool0[ans].x = t->x;
pool0[ans].l = seg0_cpy(t->l);
pool0[ans].r = seg0_cpy(t->r);
return ans;
#undef t
}
void up1(int p1, int p0, ll x, int t, int b=0, int e=1e9)
{
#define t (pool1+t)
if (e-b == 1) {
if (!t->x) t->x = new_node0();
up0(p0, x, t->x);
return;
}
if (p1 < (b+e)/2) {
if (!t->l) t->l = new_node1();
up1(p1, p0, x, t->l, b, (b+e)/2);
} else {
if (!t->r) t->r = new_node1();
up1(p1, p0, x, t->r, (b+e)/2, e);
}
if (t->l && t->r) {
if (!t->x) {
int u = p1 < (b+e)/2? t->r: t->l;
while (!pool1[u].x)
u = pool1[u].l? pool1[u].l: pool1[u].r;
t->x = seg0_cpy(pool1[u].x);
}
int ul = t->l, ur = t->r;
while (!pool1[ul].x)
ul = pool1[ul].l? pool1[ul].l: pool1[ul].r;
while (!pool1[ur].x)
ur = pool1[ur].l? pool1[ur].l: pool1[ur].r;
merge0(p0, pool1[ul].x, pool1[ur].x, t->x);
}
#undef t
}
ll get1(int l1, int r1, int l0, int r0, int t, int b=0, int e=1e9)
{
if (r1 <= b || e <= l1 || !t)
return 0;
#define t (pool1+t)
if (l1 <= b && e <= r1) {
if (!t->x) {
if (t->l)
return get1(l1,r1,l0,r0, t->l, b, (b+e)/2);
else
return get1(l1,r1,l0,r0, t->r, (b+e)/2, e);
} else {
return get0(l0, r0, t->x);
}
}
return __gcd(get1(l1, r1, l0, r0, t->l, b, (b+e)/2),
get1(l1, r1, l0, r0, t->r, (b+e)/2, e));
#undef t
}
int rt = new_node1();
void init(int R, int C)
{
}
void update(int P, int Q, long long K)
{
up1(P, Q, K, rt);
}
long long calculate(int P, int Q, int U, int V)
{
int l1 = min(P, U);
int r1 = max(P, U) + 1;
int l0 = min(Q, V);
int r0 = max(Q, V) + 1;
return get1(l1, r1, l0, r0, rt);
}
