#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> st;
int n, m;
void buildy(int vx, int vy, int lx, int rx, int ly, int ry) {
if (ly==ry) {
if (lx==rx) {
st[vx][vy]=0;
} else {
st[vx][vy]=__gcd(st[vx*2][vy], st[vx*2+1][vy]);
}
} else {
int midy=ly+(ry-ly)/2;
buildy(vx, vy*2, lx, rx, ly, midy);
buildy(vx, vy*2+1, lx, rx, midy+1, ry);
st[vx][vy]=__gcd(st[vx][vy*2], st[vx][vy*2+1]);
}
}
void buildx(int vx, int lx, int rx) {
if (lx!=rx) {
int midx=lx+(rx-lx)/2;
buildx(vx*2, lx, midx);
buildx(vx*2+1, midx+1, rx);
}
buildy(vx, 1, lx, rx, 0, m-1);
}
int queryy(int vx, int vy, int ly, int ry, int qly, int qry) {
if (ly>qry || ry<qly) return 0;
if (ly>=qly && ry<=qry) {
return st[vx][vy];
}
int midy=ly+(ry-ly)/2;
int s1=queryy(vx, vy*2, ly, midy, qly, qry);
int s2=queryy(vx, vy*2+1, midy+1, ry, qly, qry);
return __gcd(s1, s2);
}
int queryx(int vx, int lx, int rx, int qlx, int qrx, int qly, int qry) {
if (lx>qrx || rx<qlx) return 0;
if (lx>=qlx && rx<=qrx) {
return queryy(vx, 1, 0, m-1, qly, qry);
}
int midx=lx+(rx-lx)/2;
int s1=queryx(vx*2, lx, midx, qlx, qrx, qly, qry);
int s2=queryx(vx*2+1, midx+1, rx, qlx, qrx, qly, qry);
return __gcd(s1, s2);
}
void updatey(int vx, int vy, int lx, int rx, int ly, int ry, int qly, int qry, int value) {
if (ly>qry || ry<qly) return;
if (ly==ry) {
if (lx==rx) {
st[vx][vy]=value;
} else {
st[vx][vy]=__gcd(st[vx*2][vy], st[vx*2+1][vy]);
}
return;
}
int midy=ly+(ry-ly)/2;
updatey(vx, vy*2, lx, rx, ly, midy, qly, qry, value);
updatey(vx, vy*2+1, lx, rx, midy+1, ry, qly, qry, value);
st[vx][vy]=__gcd(st[vx][vy*2], st[vx][vy*2+1]);
return;
}
void updatex(int vx, int vy, int lx, int rx, int qlx, int qrx, int qry, int qly, int value) {
if (lx>qrx || rx<qlx) return;
if (lx!=rx) {
int midx=lx+(rx-lx)/2;
updatex(vx*2, vy, lx, midx, qlx, qrx, qly, qry, value);
updatex(vx*2+1, vy, midx+1, rx, qlx, qrx, qly, qry, value);
}
updatey(vx, vy, lx, rx, 0, m-1, qly, qry, value);
return;
}
#undef int
void init(int R, int C) {
#define int long long
n=R, m=C;
st.resize(4*n, vector<int> (4*m, 0));
//buildx(1, 0, n-1);
#undef int
}
void update(int P, int Q, long long K) {
#define int long long
updatex(1, 1, 0, n-1, P, P, Q, Q, K);
#undef int
}
long long calculate(int P, int Q, int U, int V) {
#define int long long
return queryx(1, 0, n-1, P, U, Q, V);
#undef int
}
