#include "game.h"
#include <bits/stdc++.h>
using namespace std;
long long gcd2(long long X, long long Y) {
return __gcd(X, Y);
}
struct y_node{
y_node() : l(0), r(0), left(NULL), right(NULL), a(0LL) {};
y_node(int l, int r) : l(l), r(r), left(NULL), right(NULL), a(0LL) {};
int l, r;
long long a = 0;
y_node *left = 0, *right = 0;
};
struct x_node{
long long a = 0;
x_node *left = 0, *right = 0;
y_node y_tree;
};
int R, C;
long long get(y_node *v){
if(!v) return 0;
return v->a;
}
long long get(x_node *v){
if(!v) return 0;
return v->a;
}
x_node *root;
void update_y(int y, long long K, y_node *v){
int ll = v->l, rr = v->r, m = (ll + rr) / 2;
if(ll == rr){
v->a = K;
return;
}
y_node **child = &(y <= m ? v->left : v->right);
if(*child == 0){
*child = new y_node(y, y);
(*child)->a = K;
}else if((*child)->l <= y && y <= (*child)->r){
update_y(y, K, *child);
}else{
do{
if(y <= m) rr = m;
else ll = m + 1;
m = (ll + rr) / 2;
}while((y <= m) == ((*child)->r <= m));
y_node *ny = new y_node(ll, rr);
if((*child)->r <= m) ny->left = *child;
else ny->right = *child;
*child = ny;
update_y(y, K, *child);
}
v->a = gcd2(get(v->left), get(v->right));
}
long long calc_y(int qy1, int qy2, y_node *v){
if(!v || qy1 > v->r || v->l > qy2) return 0;
if(qy1 <= v->l && v->r <= qy2) return v->a;
return gcd2(calc_y(qy1, qy2, v->left), calc_y(qy1, qy2, v->right));
}
void update_x(int x, int y, long long K, x_node *v, int x1 = 0, int x2 = R - 1){
if(x1 == x2){
if(v->y_tree.a == 0) v->y_tree = y_node(0, C - 1);
update_y(y, K, &v->y_tree);
return;
}
int xm = (x1 + x2) / 2;
if(x <= xm){
if(!v->left) v->left = new x_node();
update_x(x, y, K, v->left, x1, xm);
}else{
if(!v->right) v->right = new x_node();
update_x(x, y, K, v->right, xm + 1, x2);
}
long long A = gcd2(v->left ? calc_y(y, y, &v->left->y_tree) : 0,
v->right ? calc_y(y, y, &v->right->y_tree) : 0);
if(v->y_tree.a == 0) v->y_tree = y_node(0, C - 1);
update_y(y, A, &v->y_tree);
}
long long calc_x(int qx1, int qx2, int qy1, int qy2, x_node *v, int x1 = 0, int x2 = R - 1){
if(!v || qx1 > x2 || x1 > qx2) return 0;
if(qx1 <= x1 && x2 <= qx2) return calc_y(qy1, qy2, &v->y_tree);
int xm = (x1 + x2) / 2;
long long a1 = 0, a2 = 0;
if(v->left) a1 = calc_x(qx1, qx2, qy1, qy2, v->left, x1, xm);
if(v->right) a2 = calc_x(qx1, qx2, qy1, qy2, v->right, xm + 1, x2);
return gcd2(a1, a2);
}
void init(int R, int C) {
root = new x_node(); ::R = R, ::C = C;
}
void update(int P, int Q, long long K) {
update_x(P, Q, K, root);
}
long long calculate(int P, int Q, int U, int V) {
return calc_x(P, U, Q, V, root);
}
