#include "game.h"
#include <bits/stdc++.h>
using namespace std;
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;
}
struct node{
long long a = 0;
node *px1 = 0, *px2 = 0, *py1 = 0, *py2 = 0;
};
int R, C;
long long get(node *v){
if(!v) return 0;
return v->a;
}
node root;
void update_y(int y, long long K, node *v, int y1, int y2){
if(y1 == y2){
v->a = K;
}else{
int ym = (y1 + y2) / 2;
if(y <= ym){
if(!v->py1) v->py1 = new node();
update_y(y, K, v->py1, y1, ym);
}else{
if(!v->py2) v->py2 = new node();
update_y(y, K, v->py2, ym + 1, y2);
}
v->a = gcd2(get(v->py1), get(v->py2));
}
}
void update_x(int x, int y, long long K, node *v, int x1, int x2, int y1, int y2){
update_y(y, K, v, y1, y2);
if(x1 != x2){
int xm = (x1 + x2) / 2;
if(x <= xm){
if(!v->px1) v->px1 = new node();
update_x(x, y, K, v->px1, x1, xm, y1, y2);
}else{
if(!v->px2) v->px2 = new node();
update_x(x, y, K, v->px2, xm + 1, x2, y1, y2);
}
}
}
long long calc_y(int qy1, int qy2, node *v, int y1, int y2){
if(qy1 > y2 || y1 > qy2) return 0;
if(qy1 <= y1 && y2 <= qy2) return v->a;
int ym = (y1 + y2) / 2;
int a1 = 0, a2 = 0;
if(v->py1) a1 = calc_y(qy1, qy2, v->py1, y1, ym);
if(v->py2) a2 = calc_y(qy1, qy2, v->py2, ym + 1, y2);
return gcd2(a1, a2);
}
long long calc_x(int qx1, int qx2, int qy1, int qy2, node *v, int x1, int x2, int y1, int y2){
if(qx1 > x2 || x1 > qx2) return 0;
if(qx1 <= x1 && x2 <= qx2) return calc_y(qy1, qy2, v, y1, y2);
int xm = (x1 + x2) / 2;
int a1 = 0, a2 = 0;
if(v->px1) a1 = calc_x(qx1, qx2, qy1, qy2, v->px1, x1, xm, y1, y2);
if(v->px2) a2 = calc_x(qx1, qx2, qy1, qy2, v->px2, xm + 1, x2, y1, y2);
return gcd2(a1, a2);
}
void init(int R, int C) {
root = node(); ::R = R, ::C = C;
}
void update(int P, int Q, long long K) {
update_x(P, Q, K, &root, 0, R - 1, 0, C - 1);
}
long long calculate(int P, int Q, int U, int V) {
return calc_x(P, U, Q, V, &root, 0, R - 1, 0, C - 1);
}
