#include "game.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2005;
int r, c;
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;
}
struct segment {
ll t[N * 4];
void upd (int l, int r, int idx, int pos, ll val) {
if (l == r) return void(t[idx] = val);
int mid = (l + r) >> 1;
if (pos <= mid) upd(l, mid, idx * 2 + 1, pos, val);
else upd(mid + 1, r, idx * 2 + 2, pos, val);
t[idx] = gcd2(t[idx * 2 + 1], t[idx * 2 + 2]);
}
ll qr (int l, int r, int idx, int tl, int tr) {
if (l > tr || r < tl) return 0;
if (l >= tl && r <= tr) return t[idx];
int mid = (l + r) >> 1;
return gcd2(qr(l, mid, idx * 2 + 1, tl, tr), qr(mid + 1, r, idx * 2 + 2, tl, tr));
}
};
struct segment2 {
segment t[N * 4];
ll get (segment t, int posy) {
return t.qr(0, c - 1, 0, posy, posy);
}
void upd (int l, int r, int idx, int posx, int posy, ll val) {
if (l < r) {
int mid = (l + r) >> 1;
if (posx <= mid) upd(l, mid, idx * 2 + 1, posx, posy, val);
else upd(mid + 1, r, idx * 2 + 2, posx, posy, val);
val = gcd2(get(t[idx * 2 + 1], posy), get(t[idx * 2 + 2], posy));
}
t[idx].upd(0, c - 1, 0, posy, val);
}
ll qr (int l, int r, int idx, int tlx, int trx, int tly, int _try) {
if (l > trx || r < tlx) return 0;
if (l >= tlx && r <= trx) return t[idx].qr(0, c - 1, 0, tly, _try);
int mid = (l + r) >> 1;
return gcd2(qr(l, mid, idx * 2 + 1, tlx, trx, tly, _try), qr(mid + 1, r, idx * 2 + 2, tlx, trx, tly, _try));
}
} segm;
void init(int R, int C) {
r = R; c = C;
/* ... */
}
void update(int P, int Q, long long K) {
segm.upd(0, r - 1, 0, P, Q, K);
/* ... */
}
long long calculate(int P, int Q, int U, int V) {
/* ... */
return segm.qr(0, r - 1, 0, P, U, Q, V);
}
