// In the name of Allah
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m;
const int maxn = 2000 + 7;
const int sq = 100;
vector<ll> A[maxn], t[2 * maxn];
void set_val(int ind, int v, int tl, int tr, int i, ll x) {
if (i >= tr || i < tl) return ;
if (tr - tl == 1) {
t[ind][v] = x;
return ;
}
int mid = (tl + tr) / 2;
set_val(ind, 2 * v + 1, tl, mid, i, x);
set_val(ind, 2 * v + 2, mid, tr, i, x);
t[ind][v] = __gcd(t[ind][2 * v + 1], t[ind][2 * v + 2]);
}
ll get_gcd(int ind, int v, int tl, int tr, int l, int r) {
l = max(l, tl); r = min(r, tr);
if (l >= tr || r <= tl) return 0;
if (l == tl && r == tr) return t[ind][v];
int mid = (tl + tr) / 2;
return __gcd(get_gcd(ind, 2 * v + 1, tl, mid, l, r), get_gcd(ind, 2 * v + 2, mid, tr, l, r));
}
void init(int R, int C) {
n = R; m = C;
int sz = n + ((n - 1) / sq);
for (int i = 0; i <= sz; i++) {
t[i].resize(4 * m);
A[i].resize(m);
}
return ;
}
void update(int i, int j, ll R) {
if (n >= maxn) return ;
set_val(i, 0, 0, m, j, R);
A[i][j] = R; ll x = 0;
int lx = (i / sq), rx = min(n, (i / sq) + sq);
for (int k = lx; k < rx; k++) x = __gcd(x, A[k][j]);
set_val(n + (i / sq), 0, 0, m, j, x);
}
ll calculate(int l1, int l2, int r1, int r2) {
r1++; r2++;
if (n >= maxn) return 0;
ll res = 0;
if (r1 - l1 <= 2 * sq) {
for (int i = l1; i < r1; i++) {
res = __gcd(res, get_gcd(i, 0, 0, m, l2, r2));
}
}
else {
int lx = (l1 / sq) + (l1 % sq != 0), rx = r1 / sq;
lx *= sq; rx *= sq;
for (int i = l1; i < lx; i++) {
res = __gcd(res, get_gcd(i, 0, 0, m, l2, r2));
}
for (int i = lx; i < rx; i += sq) {
res = __gcd(res, get_gcd(n + (i / sq), 0, 0, m, l2, r2));
}
for (int i = rx; i < r1; i++) {
res = __gcd(res, get_gcd(i, 0, 0, m, l2, r2));
}
}
return res;
}
