#include<bits/stdc++.h>
#include "game.h"
#define int long long
using namespace std;
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 ST{
vector<int> arr;
ST(){}
ST(int N){
arr = vector<int> (4 * N);
}
int u(int idx, int l, int r, int qidx, int qval){
if(r < qidx || l > qidx) return arr[idx];
if(l == r && qidx == l){
arr[idx] = qval;
return arr[idx];
}
int m = (l + r) / 2;
arr[idx] = gcd2(u(idx * 2, l, m, qidx, qval), u(idx * 2 + 1, m + 1, r, qidx, qval));
// cout << arr[idx] << " " << l << " " << r << endl;
return arr[idx];
}
int q(int idx, int l, int r, int ql, int qr){
if(l > qr || r < ql) return 0;
if(l >= ql && r <= qr) return arr[idx];
int m = (l + r) / 2;
return gcd2(q(idx * 2, l, m, ql, qr), q(idx * 2 + 1, m + 1, r, ql, qr));
}
};
int R, C;
vector<ST> sts;
void init(signed _R, signed _C) {
R = _R;
C = _C;
sts = vector<ST> (R, ST(C));
}
void update(signed P, signed Q, int K) {
sts[P].u(1,0,C-1,Q,K);
}
long long calculate(signed P, signed Q, signed U, signed V) {
int res = 0;
for(int i = P; i <= U; i++){
res = gcd2(res, sts[i].q(1,0,C-1,Q,V));
}
return res;
}
