#include <bits/stdc++.h>
#include "game.h"
using namespace std;
class hor {
public:
hor* l;
hor* r;
int y;
long long g;
hor(int y = -1): y(y) {
l = r = NULL;
g = 0;
}
};
class ver {
public:
ver* l;
ver* r;
hor* h;
ver() {
l = r = NULL;
h = NULL;
}
};
ver* root;
int n, m;
inline long long gcd(long long a, long long b) {
if (!a || !b) {
return a ^ b;
} else {
int shift = __builtin_ctzll(a | b);
b >>= __builtin_ctzll(b);
while (a) {
a >>= __builtin_ctzll(a);
if (a < b) {
swap(a, b);
}
a -= b;
}
return b << shift;
}
}
long long query(hor* root, int l, int r, int yl, int yr) {
if (root == NULL) {
return 0;
}
if (root->y != -1) {
return yl <= root->y && root->y <= yr ? root->g : 0;
}
if (yl <= l && r <= yr) {
return root->g;
} else {
int mid = (l + r) >> 1;
long long ans = 0;
if (yl <= mid) {
ans = gcd(ans, query(root->l, l, mid, yl, yr));
}
if (yr > mid) {
ans = gcd(ans, query(root->r, mid + 1, r, yl, yr));
}
return ans;
}
}
long long query(ver* root, int l, int r, int xl, int xr, int yl, int yr) {
if (root == NULL) {
return 0;
}
if (xl <= l && r <= xr) {
return query(root->h, 0, m - 1, yl, yr);
} else {
int mid = (l + r) >> 1;
long long ans = 0;
if (xl <= mid) {
ans = gcd(ans, query(root->l, l, mid, xl, xr, yl, yr));
}
if (xr > mid) {
ans = gcd(ans, query(root->r, mid + 1, r, xl, xr, yl, yr));
}
return ans;
}
}
void modify(hor* root, int l, int r, int y, long long g) {
int mid = (l + r) >> 1;
if (root->y != -1) {
if (root->y == y) {
root->g = g;
return;
} else {
if (root->y <= mid) {
root->l = new hor(root->y);
root->l->g = root->g;
} else {
root->r = new hor(root->y);
root->r->g = root->g;
}
root->y = -1;
}
}
if (y <= mid) {
if (root->l == NULL) {
root->l = new hor(y);
}
modify(root->l, l, mid, y, g);
} else {
if (root->r == NULL) {
root->r = new hor(y);
}
modify(root->r, mid + 1, r, y, g);
}
root->g = gcd(root->l == NULL ? 0 : root->l->g, root->r == NULL ? 0 : root->r->g);
}
void modify(ver* root, int l, int r, int x, int y, long long g) {
if (root->h == NULL) {
root->h = new hor(y);
}
if (l == r) {
modify(root->h, 0, m - 1, y, g);
} else {
if (root->l == NULL) {
root->l = new ver();
}
if (root->r == NULL) {
root->r = new ver();
}
int mid = (l + r) >> 1;
if (x <= mid) {
modify(root->l, l, mid, x, y, g);
} else {
modify(root->r, mid + 1, r, x, y, g);
}
modify(root->h, 0, m - 1, y, gcd(query(root->l->h, 0, m - 1, y, y), query(root->r->h, 0, m - 1, y, y)));
}
}
void init(int R, int C) {
n = R;
m = C;
root = new ver();
}
void update(int P, int Q, long long K) {
modify(root, 0, n - 1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return query(root, 0, n - 1, P, U, Q, V);
}
