#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int row, col;
struct Seg{
struct Node {
int l, r;
ll val;
Node *lc, *rc;
Node () {
l = 0;
r = 0;
val = 0;
lc = nullptr;
rc = nullptr;
}
Node (int _l, int _r) {
l = _l;
r = _r;
val = 0;
lc = nullptr;
rc = nullptr;
}
void update(int pos, ll x) {
if (l == r) {
val = x;
return;
}
int mid = l + r >> 1;
if (pos <= mid) {
if (!lc) {
lc = new Node(l, mid);
}
lc -> update(pos, x);
}
else {
if (!rc) {
rc = new Node(mid + 1, r);
}
rc -> update(pos, x);
}
val = __gcd(lc ? lc -> val : 0, rc ? rc -> val : 0);
}
ll get(int u, int v) {
if (u <= l && r <= v) {
return val;
}
int mid = l + r >> 1;
if (v < mid + 1) {
return lc ? lc -> get(u, v) : 0;
}
if (u > mid) {
return rc ? rc -> get(u, v) : 0;
}
return __gcd(lc ? lc -> get(u, v) : 0, rc ? rc -> get(u, v) : 0);
}
};
int l, r;
Seg *lc, *rc;
Node *root;
Seg() {
l = 0;
r = 0;
lc = nullptr;
rc = nullptr;
root = nullptr;
}
Seg(int _l, int _r) {
l = _l;
r = _r;
lc = nullptr;
rc = nullptr;
root = new Node(1, col);
}
void update(int u, int v, ll x) {
if (l == r) {
root -> update(v, x);
return;
}
int mid = l + r >> 1;
if (mid >= u) {
if (!lc) {
lc = new Seg(l, mid);
}
lc -> update(u, v, x);
}
else {
if (!rc) {
rc = new Seg(mid + 1, r);
}
rc -> update(u, v, x);
}
ll j = __gcd(lc ? lc -> root -> get(v, v) : 0, rc ? rc -> root -> get(v, v) : 0);
// cerr << l << " " << r << " " << u << " " << v << " " << j << "\n";
root -> update(v, j);
}
ll get(int p, int q, int u, int v) {
if (p <= l && r <= u) {
// cerr << l << " " << r << " " << root -> get(q, v) << "\n";
return root -> get(q, v);
}
int mid = l + r >> 1;
if (mid + 1 > u) {
return lc ? lc -> get(p, q, u, v) : 0;
}
if (mid < p) {
return rc ? rc -> get(p, q, u, v) : 0;
}
return __gcd(lc ? lc -> get(p, q, u, v) : 0, rc ? rc -> get(p, q, u, v) : 0);
}
};
Seg *root = nullptr;
void init(int R, int C) {
row = R;
col = C;
// cerr << "init " << R << " " << C << "\n";
root = new Seg(1, row);
}
void update(int P, int Q, long long K) {
P ++;
Q ++;
// cerr << "update " << P << " " << Q << " " << K << "\n";
root -> update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
P ++;
Q ++;
U ++;
V ++;
// cerr << "calculate " << P << " " << Q << " " << U << " " << V << "\n";
return root -> get(P, Q, U, V);
}
