#include <bits/stdc++.h>
#include "game.h"
using namespace std;
constexpr int N = 2001;
constexpr int MX = 12;
int lg[N];
struct SparseTable {
int n, m;
vector<vector<long long>> dp;
SparseTable(int _n) {
n = _n;
m = __lg(n) + 1;
dp.resize(n, vector<long long>(m));
}
void build(vector<long long> &a) {
for (int i = 0; i < n; i++) {
dp[i][0] = a[i];
}
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) {
if (i + (1 << (j - 1)) < n) {
dp[i][j] = __gcd(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
}
}
}
long long get(int l, int r) {
int x = lg[r - l + 1];
return __gcd(dp[l][x], dp[r - (1 << x) + 1][x]);
}
};
int n, m;
vector<vector<long long>> a;
vector<SparseTable> t;
void init(int R, int C) {
for (int i = 2; i < N; i++) {
lg[i] = lg[i / 2] + 1;
}
n = R;
m = C;
a.resize(n, vector<long long>(m));
for (int i = 0; i < n; i++) {
t.push_back(SparseTable(m));
}
}
void update(int i, int j, long long k) {
a[i][j] = k;
t[i].build(a[i]);
}
long long calculate(int p, int q, int u, int v) {
long long ans = 0;
for (int i = p; i <= u; i++) {
ans = __gcd(ans, t[i].get(q, v));
}
return ans;
}
