#ifndef __GAME_H__
#define __GAME_H__
#ifdef __cplusplus
extern "C" {
#endif
#include <math.h>
void init(int R, int C);
void update(int P, int Q, long long K);
long long calculate(int P, int Q, int U, int V);
int n, m;
long long f(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
typedef long long T;
T **tree;
T ysum(int xnode, int ynode, int ys, int ye, int yl, int yr){
if(yr < ys || ye < yl) return 0;
if(yl <= ys && ye <= yr) return tree[xnode][ynode];
int ym = (ys + ye) >> 1;
T ret = 0;
if(ys <= ym) ret = f(ret, ysum(xnode, ynode*2, ys, ym, yl, yr));
if(ym+1 <= ye) ret = f(ret, ysum(xnode, ynode*2+1, ym+1, ye, yl, yr));
return ret;
}
T xsum(int xnode, int xs, int xe, int xl, int xr, int yl, int yr){
if(xr < xs || xe < xl) return 0;
if(xl <= xs && xe <= xr) return ysum(xnode, 1, 0, m-1, yl, yr);
int xm = (xs + xe) >> 1;
T ret = 0;
if(xs <= xm) ret = f(ret, xsum(xnode*2, xs, xm, xl, xr, yl, yr));
if(xm+1 <= xe) ret = f(ret, xsum(xnode*2+1, xm+1, xe, xl, xr, yl, yr));
return ret;
}
void yupdate(int xnode, int xs, int xe, int ynode, int ys, int ye, int x, int y, T val){
if(ye < y || y < ys) return;
if(ys^ye){
int ym = (ys + ye) >> 1;
if(y <= ym) yupdate(xnode, xs, xe, ynode*2, ys, ym, x, y, val);
else yupdate(xnode, xs, xe, ynode*2+1, ym+1, ye, x, y, val);
tree[xnode][ynode] = f(tree[xnode][ynode*2], tree[xnode][ynode*2+1]);
}else{
if(xs^xe) tree[xnode][ynode] = f(tree[xnode*2][ynode], tree[xnode*2+1][ynode]);
else tree[xnode][ynode] = val;
}
}
void xupdate(int xnode, int xs, int xe, int x, int y, T val){
if(xe < x || x < xs) return;
if(xs^xe){
int xm = (xs + xe) >> 1;
if(x <= xm) xupdate(xnode*2, xs, xm, x, y, val);
else xupdate(xnode*2+1, xm+1, xe, x, y, val);
}
yupdate(xnode, xs, xe, 1, 0, m-1, x, y, val);
}
void init(int R, int C) {
n = R, m = C;
int u = 1, v = 1;
while(u < n) u <<= 1;
while(v < m) v <<= 1;
u = u*2+5, v = v*2+5;
tree = new T*[u];
for(int i=0; i<u; i++){
tree[i] = new T[v];
for(int j=0; j<m; j++) tree[i][j] = 0LL;
}
}
void update(int x, int y, long long val) {
xupdate(1, 0, n-1, x, y, val);
}
long long calculate(int x1, int y1, int x2, int y2) {
return xsum(1, 0, n-1, x1, x2, y1, y2);
}
#ifdef __cplusplus
}
#endif
#endif /* __GAME_H__ */
