#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
struct Seggy{
vector<ll> s;
void init(int n){
s.resize(4 * n, 0);
}
void upd(int k,int tl,int tr,int p,ll v){
if(tl == tr){
s[k] = v;
return;
}
int tm = (tl + tr) / 2;
if(p <= tm)upd(k *2, tl, tm, p, v);
else upd(k *2 + 1, tm + 1, tr, p, v);
s[k] = __gcd(s[k * 2], s[k * 2 + 1]);
}
ll qry(int k,int tl,int tr,int l,int r){
if(l > tr || tl > r)return 0;
if(l <= tl && tr <= r)return s[k];
int tm = (tl +tr) / 2;
return __gcd(qry(k * 2,tl, tm, l, r), qry(k *2 + 1, tm + 1, tr, l, r));
}
};
vector<Seggy> seg;
int n, m;
void init(signed R, signed C) {
n = R, m = C;
seg.resize(R);
for(auto &u: seg)u.init(C);
}
void update(signed P, signed Q, long long K) {
seg[P].upd(1, 0, m - 1, Q, K);
}
long long calculate(signed P, signed Q, signed U, signed V) {
int g = 0;
for(int i = P;i <= U;i++){
g = __gcd(g, seg[i].qry(1, 0,m - 1,Q, V));
}
return g;
}
#define int signed
