#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;
vi lp, rp;
Seg1() {}
Seg1(int m): n(m) {
Add();
}
inline void Add() {
seg.push_back(0);
lp.push_back(0);
rp.push_back(0);
}
inline void Fix(int i) {
if (!lp[i]) {
lp[i] = seg.size();
Add();
rp[i] = seg.size();
Add();
}
}
void update(int i, ll x, int ind, int l, int r) {
if (l + 1 == r) {
seg[ind] = x;
return;
}
Fix(ind);
if (i < (l + r) >> 1) {
update(i, x, lp[ind], l, (l + r) >> 1);
} else {
update(i, x, rp[ind], (l + r) >> 1, r);
}
seg[ind] = gcd2(seg[lp[ind]], seg[rp[ind]]);
}
inline void update(int i, ll x) {
update(i, x, 0, 0, n);
}
ll query(int a, int b, int ind, int l, int r) {
if (a <= l && r <= b) return seg[ind];
if (r <= a || b <= l || !lp[ind]) return 0;
return gcd2(query(a, b, lp[ind], l, (l + r) >> 1), query(a, b, rp[ind], (l + r) >> 1, r));
}
inline ll query(int a, int b) {
return query(a, b, 0, 0, n);
}
};
struct Seg2 {
int n, m;
vector<Seg1> seg;
vi lp, rp;
Seg2() {}
Seg2(int n, int m): n(n), m(m) {
Add();
}
inline void Add() {
seg.push_back(Seg1(m));
lp.push_back(0);
rp.push_back(0);
}
inline void Fix(int i) {
if (!lp[i]) {
lp[i] = seg.size();
Add();
rp[i] = seg.size();
Add();
}
}
void update(int i, int j, ll x, int ind, int l, int r) {
if (l + 1 == r) {
seg[ind].update(j, x);
return;
}
Fix(ind);
if (i < (l + r) >> 1) {
update(i, j, x, lp[ind], l, (l + r) >> 1);
} else {
update(i, j, x, rp[ind], (l + r) >> 1, r);
}
x = gcd2(seg[lp[ind]].query(j, j + 1), seg[rp[ind]].query(j, j + 1));
seg[ind].update(j, x);
}
inline void update(int i, int j, ll x) {
update(i, j, x, 0, 0, n);
}
ll query(int x1, int y1, int x2, int y2, int ind, int l, int r) {
if (x1 <= l && r <= x2) return seg[ind].query(y1, y2);
if (r <= x1 || x2 <= l || !lp[ind]) return 0;
return gcd2(query(x1, y1, x2, y2, lp[ind], l, (l + r) >> 1), query(x1, y1, x2, y2, rp[ind], (l + r) >> 1, r));
}
inline ll query(int x1, int y1, int x2, int y2) {
return query(x1, y1, x2, y2, 0, 0, n);
}
};
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);
}
