#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int n, m;
struct TwoDimSegTree{
long long **tree;
void set(int n = 0, int m = 0){
tree = (long long**)malloc(n * 4 * sizeof(long long*));
for(int i = 0; i < n * 4; i++) tree[i] = (long long*)malloc(m * 4 * sizeof(long long));
}
long long queryy(int vx, int vy, int tly, int try_, int ly, int ry){
if(ly > ry) return 0;
else if(ly == tly && ry == try_) return tree[vx][vy];
else{
int tmy = tly + (try_ - tly) / 2;
return __gcd(queryy(vx, vy * 2, tly, tmy, ly, min(ry, tmy)), queryy(vx, vy * 2 + 1, tmy + 1, try_, max(ly, tmy + 1), ry));
}
}
long long queryx(int vx, int tlx, int trx, int lx, int rx, int ly, int ry){
if(lx > rx) return 0;
else if(lx == tlx && rx == trx) return queryy(vx, 1, 0, m - 1, ly, ry);
else{
int tmx = tlx + (trx - tlx) / 2;
return __gcd(queryx(vx * 2, tlx, tmx, lx, min(rx, tmx), ly, ry), queryx(vx * 2 + 1, tmx + 1, trx, max(lx, tmx + 1), rx, ly, ry));
}
}
void updatey(int vx, int lx, int rx, int vy, int ly, int ry, int posy, long long val){
if(ly == ry){
if(lx == rx) tree[vx][vy] = val;
else tree[vx][vy] = __gcd(tree[vx * 2][vy], tree[vx * 2 + 1][vy]);
}
else{
int my = ly + (ry - ly) / 2;
if(posy <= my) updatey(vx, lx, rx, vy * 2, ly, my, posy, val);
else updatey(vx, lx, rx, vy * 2 + 1, my + 1, ry, posy, val);
tree[vx][vy] = __gcd(tree[vx][vy * 2], tree[vx][vy * 2 + 1]);
}
}
void updatex(int vx, int lx, int rx, int posx, int posy, long long val){
if(lx != rx){
int mx = lx + (rx - lx) / 2;
if(posx <= mx) updatex(vx * 2, lx, mx, posx, posy, val);
else updatex(vx * 2 + 1, mx + 1, rx, posx, posy, val);
}
updatey(vx, lx, rx, 1, 0, m - 1, posy, val);
}
};
TwoDimSegTree sgt;
void init(int R, int C){
n = R, m = C;
sgt.set(n, m);
}
void update(int P, int Q, long long K) {
sgt.updatex(1, 0, n - 1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return sgt.queryx(1, 0, n - 1, P, U, Q, V);
}
