#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using ll = long long;
using ull = unsigned long long;
#define mid ((l+r)>>1)
mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());
int R, C;
struct treap {
treap *lc, *rc;
ull pri;
int pos;
ll val, ans;
treap(int pos, ll val):
lc(NULL), rc(NULL), pri(rng()), pos(pos), val(val), ans(val) {}
inline void pull() {
ans = 0;
if(lc) ans = __gcd(ans, lc->ans);
if(rc) ans = __gcd(ans, rc->ans);
ans = __gcd(ans, val);
}
};
treap *merge(treap *u, treap *v) {
if(!u) return v;
if(!v) return u;
if(u->pri>v->pri) {
u->rc = merge(u->rc, v);
return u->pull(), u;
}
v->lc = merge(u, v->lc);
return v->pull(), v;
}
void split(treap *v, int x, treap *&l, treap *&r) {
if(!v) { l=NULL; r=NULL; return; }
if(v->pos<=x) {
split(v->rc, x, v->rc, r);
(l=v)->pull();
}
else {
split(v->lc, x, l, v->lc);
(r=v)->pull();
}
}
void upd(treap *&v, int p, ll x) {
treap *A, *B, *C;
split(v, p-1, A, B);
split(B, p, B, C);
if(B) B->val = B->ans = x;
else B = new treap(p, x);
v = merge(merge(A, B), C);
}
ll get(treap *&v, int s, int e) {
treap *A, *B, *C;
split(v, s-1, A, B);
split(B, e-1, B, C);
ll ans = B ? B->ans : 0;
v = merge(merge(A, B), C);
return ans;
}
struct seg {
seg *lc, *rc;
treap *ds;
seg(): lc(NULL), rc(NULL), ds(NULL) {}
};
ll upd2(int p, int q, ll x, seg *v, int l=0, int r=R) {
if(r-l == 1) {
upd(v->ds, q, x);
return x;
}
ll val=0;
if(p<mid) {
if(!v->lc) v->lc = new seg();
val = __gcd(upd2(p, q, x, v->lc, l, mid), v->rc ? get(v->rc->ds, q, q+1) : 0);
}
else {
if(!v->rc) v->rc = new seg();
val = __gcd(v->lc ? get(v->lc->ds, q, q+1) : 0, upd2(p, q, x, v->rc, mid, r));
}
upd(v->ds, q, val);
return val;
}
ll get2(int s1, int e1, int s2, int e2, seg *v, int l=0, int r=R) {
if(s1>=r || l>=e1 || !v) return 0;
if(s1<=l && r<=e1) return get(v->ds, s2, e2);
return __gcd(
get2(s1, e1, s2, e2, v->lc, l, mid),
get2(s1, e1, s2, e2, v->rc, mid, r)
);
}
seg *ds;
void init(int R, int C) {
::R = R;
::C = C;
ds = new seg();
}
void update(int P, int Q, long long K) {
upd2(P, Q, K, ds);
}
long long calculate(int P, int Q, int U, int V) {
return get2(P, U+1, Q, V+1, ds);
}
