#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;
node0 *l, *r;
} pool0[10000000];
struct node1 {
node0 x;
node1 *l, *r;
} pool1[10000000];
node0 *new_node0(){static int nxt=0; return &pool0[nxt++];}
node1 *new_node1(){static int nxt=0; return &pool1[nxt++];}
void up0(int p, ll x, node0 *t, int b=0, int e=1e9)
{
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? t->l->x: 0, t->r? t->r->x: 0);
}
void merge0(int p, node0 *l, node0 *r, node0 *t, int b=0, int e=1e9)
{
t->x = __gcd(l? l->x: 0, r? r->x: 0);
if (e-b == 1)
return;
if (p < (b+e)/2) {
if (!t->l) t->l = new_node0();
merge0(p, l? l->l: NULL, r? r->l: NULL, t->l, b, (b+e)/2);
} else {
if (!t->r) t->r = new_node0();
merge0(p, l? l->r: NULL, r? r->r: NULL, t->r, (b+e)/2, e);
}
}
ll get0(int l, int r, node0 *t, int b=0, int e=1e9)
{
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));
}
void up1(int p1, int p0, ll x, node1 *t, int b=0, int e=1e9)
{
if (e-b == 1) {
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);
}
merge0(p0, t->l? &t->l->x: NULL, t->r? &t->r->x: NULL, &t->x);
}
ll get1(int l1, int r1, int l0, int r0, node1 *t, int b=0, int e=1e9)
{
if (r1 <= b || e <= l1 || !t)
return 0;
if (l1 <= b && e <= r1)
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));
}
node1 *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);
}
