#include "game.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
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;
}
const int MAX_N = 2005;
struct Seg1 {
int n;
vi seg;
Seg1() {}
Seg1(int m) {
for (n = 1; n < m; n <<= 1);
seg.resize(2 * n);
}
void update(int i, int x) {
seg[i += n] = x;
for (i >>= 1; i; i >>= 1) {
seg[i] = gcd2(seg[i << 1], seg[i << 1 | 1]);
}
}
ll query(int l, int r) {
ll x = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) x = gcd2(x, seg[l++]);
if (r & 1) x = gcd2(x, seg[--r]);
}
return x;
}
};
vector<Seg1> mat;
int n, m;
void init(int R, int C) {
n = R, m = C;
mat.resize(n, Seg1(m));
}
void update(int p, int q, long long k) {
mat[p].update(q, k);
}
long long calculate(int p, int q, int u, int v) {
ll x = 0;
for (int i = p; i <= u; i++) {
x = gcd2(x, mat[i].query(q, v + 1));
}
return x;
}
