#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = long long;
int R, C;
class Segtree1d {
// 1d, dynamic
private:
struct node {
ll ans;
node *l, *r;
node() : ans(0), l(nullptr), r(nullptr) {}
void pull() {
ans = __gcd( l ? l->ans : 0, r ? r->ans : 0);
}
} *root;
void modify(int pos, ll v, node *&cur, int l, int r) {
if(!cur) cur = new node();
if(l+1 == r) {
cur->ans = v;
return;
}
int m = l+(r-l)/2;
if(pos < m)
modify(pos, v, cur->l, l, m);
else
modify(pos, v, cur->r, m, r);
cur->pull();
}
ll query(int ql, int qr, node *cur, int l, int r) {
if(l >= qr || r <= ql || !cur) return 0;
if(ql <= l && r <= qr) return cur->ans;
int m = l+(r-l)/2;
return __gcd(query(ql, qr, cur->l, l, m), query(ql, qr, cur->r, m, r));
}
public:
Segtree1d() : root(nullptr) {}
void modify(int pos, ll v) {
modify(pos, v, root, 0, C);
}
ll query(int l, int r) {
return query(l, r, root, 0, C);
}
};
class Segtree2d {
private:
struct node {
Segtree1d st;
node *l, *r;
node() : l(nullptr), r(nullptr) {}
// Complexity of pull would TLE
// Notice that only posy would change
void pull(int y) {
st.modify(y, __gcd(l ? l->st.query(y, y+1) : 0, r ? r->st.query(y, y+1) : 0));
}
} *root;
void modify(int posx, int posy, ll v, node *&cur, int l, int r) {
if(!cur) cur = new node();
if(l+1 == r) {
cur->st.modify(posy, v);
return;
}
int m = l+(r-l)/2;
if(posx < m)
modify(posx, posy, v, cur->l, l, m);
else
modify(posx, posy, v, cur->r, m, r);
cur->pull(posy);
}
ll query(int lx, int rx, int ly, int ry, node *cur, int l, int r) {
if(r <= lx || l >= rx || !cur) return 0;
if(lx <= l && r <= rx) return cur->st.query(ly, ry);
int m = l+(r-l)/2;
return __gcd(query(lx, rx, ly, ry, cur->l, l, m), query(lx, rx, ly, ry, cur->r, m, r));
}
public:
Segtree2d() : root(nullptr) {}
void modify(int posx, int posy, ll v) {
modify(posx, posy, v, root, 0, R);
}
ll query(int lx, int rx, int ly, int ry) {
return query(lx, rx, ly, ry, root, 0, R);
}
} sgt;
void init(int r, int c) {
R = r, C = c;
}
void update(int x, int y, ll k) {
sgt.modify(x, y, k);
}
ll calculate(int lx, int ly, int rx, int ry) {
if(lx > rx) swap(lx, rx);
if(ly > ry) swap(ly, ry);
return sgt.query(lx, rx+1, ly, ry+1);
}
