#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int N, M;
struct node1D {
ll g;
node1D *L, *R;
node1D() {
L = R = NULL;
g = 0;
}
void update(int l, int r, int x, ll k) {
if(l == r) { g = k; return; }
int m = l + r >> 1;
if(x <= m) {
if(!L) L = new node1D();
L -> update(l, m, x, k);
} else {
if(!R) R = new node1D();
R -> update(m + 1, r, x, k);
}
if(L && R) g = gcd(L -> g, R -> g);
else if(L) g = L -> g;
else g = R -> g;
}
ll get(int l, int r, int i, int j) {
if(r < i || l > j) return 0;
if(i <= l && r <= j) return g;
int m = l + r >> 1;
if(L && R) {
return gcd(L -> get(l, m, i, j), R -> get(m + 1, r, i, j));
} else if(L) return L -> get(l, m, i, j);
else if(R) return R -> get(m + 1, r, i, j);
else return 0;
}
};
struct node2D {
node1D *t;
node2D *L, *R;
node2D() {
t = new node1D();
L = R = NULL;
}
void update(int l, int r, int x, int y, ll K) {
t -> update(0, M - 1, y, K);
if(l == r) return;
int m = l + r >> 1;
if(x <= m) {
if(!L) L = new node2D();
L -> update(l, m, x, y, K);
} else {
if(!R) R = new node2D();
R -> update(m + 1, r, x, y, K);
}
}
ll get(int l, int r, int x1, int y1, int x2, int y2) {
if(r < x1 || l > x2) return 0;
if(x1 <= l && r <= x2)
return t -> get(0, M - 1, y1, y2);
int m = l + r >> 1;
if(L && R) {
return gcd(L -> get(l, m, x1, y1, x2, y2), R -> get(m + 1, r, x1, y1, x2, y2));
} else if(L) return L -> get(l, m, x1, y1, x2, y2);
else if(R) return R -> get(m + 1, r, x1, y1, x2, y2);
else return 0;
}
} *root;
void init(int R, int C) {
N = R, M = C;
root = new node2D();
}
void update(int P, int Q, ll K) {
root -> update(0, N - 1, P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return root -> get(0, N - 1, P, Q, U, V);
}
