#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;
map<int, int> seg;
Seg1() {}
Seg1(int m) {
for (n = 1; n < m; n <<= 1);
}
void update(int i, ll 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;
}
};
struct Seg2 {
int n, m;
map<int, Seg1> seg;
Seg2 () {}
Seg2 (int n1, int m1) {
for (n = 1; n < n1; n <<= 1);
for (m = 1; m < m1; m <<= 1);
}
void update(int i, int j, ll x) {
i += n;
if (!seg.count(i)) {
seg[i] = Seg1(m);
}
seg[i].update(j, x);
for (i >>= 1; i; i >>= 1) {
int v1 = 0, v2 = 0;
if (seg.count(i << 1)) {
v1 = seg[i << 1].seg[m + j];
}
if (seg.count(i << 1 | 1)) {
v2 = seg[i << 1 | 1].seg[m + j];
}
x = gcd2(v1, v2);
if (!seg.count(i)) {
seg[i] = Seg1(m);
}
seg[i].update(j, x);
}
}
ll query(int x1, int y1, int x2, int y2) {
ll x = 0;
for (x1 += n, x2 += n; x1 < x2; x1 >>= 1, x2 >>= 1) {
if (x1 & 1) {
if (seg.count(x1)) {
x = gcd2(x, seg[x1].query(y1, y2));
}
x1++;
}
if (x2 & 1) {
--x2;
if (seg.count(x2)) {
x = gcd2(x, seg[x2].query(y1, y2));
}
}
}
return x;
}
};
Seg2 mat;
int n, m;
void init(int R, int C) {
n = R, m = C;
mat = Seg2(n, m);
}
void update(int p, int q, long long k) {
mat.update(p, q, k);
}
long long calculate(int p, int q, int u, int v) {
return mat.query(p, q, u + 1, v + 1);
}
