#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int r, c;
vector<vector<ll>> st;
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;
}
void change(int x, int y, ll val){
int txl = 0, txr = r-1, tyl = 0, tyr = c-1, nx = 1, ny = 1;
while (txl != txr){
int txm = (txl+txr)/2;
if (x <= txm){
nx = nx*2;
txr = txm;
}
else {
nx = nx*2+1;
txl = txm+1;
}
}
while (tyl != tyr){
int tym = (tyl+tyr)/2;
if (y <= tym){
ny = ny*2;
tyr = tym;
}
else {
ny = ny*2+1;
tyl = tym+1;
}
}
//cout << x << " " << y << " " << txl << " " << tyl << " " << nx << " " << ny << endl;
st[nx][ny] = val;
int cnx = nx;
while (cnx){
if (cnx != nx) st[cnx][ny] = gcd2(st[cnx*2][ny], st[cnx*2+1][ny]);
int cny = ny>>1;
while (cny){
st[cnx][cny] = gcd2(st[cnx][cny*2], st[cnx][cny*2+1]);
cny >>= 1;
}
cnx >>= 1;
}
}
ll queryh(int hn, int y1, int y2, int node=1, int tl=0, int tr=c-1){
if (y1 <= tl && tr <= y2) return st[hn][node];
int tm = (tl+tr)/2;
ll res = 0;
if (y1 <= tm) res = gcd2(res, queryh(hn, y1, y2, node*2, tl, tm));
if (tm+1 <= y2) res = gcd2(res, queryh(hn, y1, y2, node*2+1, tm+1, tr));
return res;
}
ll queryv(int x1, int x2, int y1, int y2, int node=1, int tl=0, int tr=r-1){
if (x1 <= tl && tr <= x2) return queryh(node, y1, y2);
int tm = (tl+tr)/2;
ll res = 0;
if (x1 <= tm) res = gcd2(res, queryv(x1, x2, y1, y2, node*2, tl, tm));
if (tm+1 <= x2) res = gcd2(res, queryv(x1, x2, y1, y2, node*2+1, tm+1, tr));
return res;
}
void init(int R, int C) {
r = R;
c = C;
st.resize(4100, vector<ll>(4100, 0));
}
void update(int P, int Q, long long K) {
change(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return queryv(P, U, Q, V);
}
