#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dimx;
int dimy;
struct NodeX {
NodeX* lft;
NodeX* rgh;
int tree_x1;
int tree_x2;
ll gcd;
NodeX(int tree_x1, int tree_x2) : lft(nullptr), rgh(nullptr), gcd(0), tree_x1(tree_x1), tree_x2(tree_x2) {}
};
struct NodeY {
NodeY* lft;
NodeY* rgh;
NodeX* xRoot;
NodeY() : lft(nullptr), rgh(nullptr), xRoot(new NodeX(1, dimx)) {}
};
ll queryX(NodeX* node, int x1, int x2) {
if (node->tree_x2 < x1 || x2 < node->tree_x1) return 0;
if (x1 <= node->tree_x1 && node->tree_x2 <= x2) return node->gcd;
ll gcd_lft = 0, gcd_rgh = 0;
int tree_mid = (node->tree_x1 + node->tree_x2) / 2;
if (x1 <= tree_mid && node->lft) gcd_lft = queryX(node->lft, x1, x2);
if (x2 >= tree_mid + 1 && node->rgh) gcd_rgh = queryX(node->rgh, x1, x2);
return __gcd(gcd_lft, gcd_rgh);
}
ll queryY(NodeY* node, int tree_y1, int tree_y2, int y1, int y2, int x1, int x2) {
if (y1 <= tree_y1 && tree_y2 <= y2) return queryX(node->xRoot, x1, x2);
ll gcd_lft = 0;
ll gcd_rgh = 0;
int tree_mid = (tree_y1 + tree_y2) / 2;
if (y1 <= tree_mid && node->lft) gcd_lft = queryY(node->lft, tree_y1, tree_mid, y1, y2, x1, x2);
if (tree_mid + 1 <= y2 && node->rgh) gcd_rgh = queryY(node->rgh, tree_mid + 1, tree_y2, y1, y2, x1, x2);
return __gcd(gcd_lft, gcd_rgh);
}
void setValueX(NodeX* node, int x, ll val) {
if (node->tree_x1 == node->tree_x2) {
node->gcd = val;
return;
}
int tree_mid = (node->tree_x1 + node->tree_x2) / 2;
if (x <= tree_mid) {
if (!node->lft) {
node->lft = new NodeX(x, x);
node->lft->gcd = val;
} else {
if (node->lft->tree_x1 <= x && x <= node->lft->tree_x2) {
setValueX(node->lft, x, val);
} else {
NodeX* child = node->lft;
/// find the LCA
int low = node->tree_x1, high = node->tree_x2;
while (low < high) {
int mid = (low + high) / 2, L, R;
L = low;
R = mid;
if (L <= x && x <= R && L <= child->tree_x1 && child->tree_x2 <= R) {
low = L;
high = R;
continue;
}
L = mid + 1;
R = high;
if (L <= x && x <= R && L <= child->tree_x1 && child->tree_x2 <= R) {
low = L;
high = R;
continue;
}
break;
}
int L = low, R = high;
NodeX* nw = new NodeX(L, R);
if (x < child->tree_x1) {
///cout << "to left\n";
nw->lft = new NodeX(x, x);
nw->lft->gcd = val;
nw->rgh = child;
} else {
///cout << "to right\n";
nw->lft = child;
nw->rgh = new NodeX(x, x);
nw->rgh->gcd = val;
}
nw->gcd = __gcd(nw->lft->gcd, nw->rgh->gcd);
node->lft = nw;
/**cout << L << " " << R << "\n";
cout << node->lft->tree_x1 << " " << node->lft->tree_x2 << " " << x << "\n";
cout << "bad 1\n";
exit(0);**/
}
}
} else {
if (!node->rgh) {
node->rgh = new NodeX(x, x);
node->rgh->gcd = val;
} else {
if (node->rgh->tree_x1 <= x && x <= node->rgh->tree_x2) {
setValueX(node->rgh, x, val);
} else {
NodeX* child = node->rgh;
/// find the LCA
int low = node->tree_x1, high = node->tree_x2;
while (low < high) {
int mid = (low + high) / 2, L, R;
L = low;
R = mid;
if (L <= x && x <= R && L <= child->tree_x1 && child->tree_x2 <= R) {
low = L;
high = R;
continue;
}
L = mid + 1;
R = high;
if (L <= x && x <= R && L <= child->tree_x1 && child->tree_x2 <= R) {
low = L;
high = R;
continue;
}
break;
}
int L = low, R = high;
NodeX* nw = new NodeX(L, R);
if (x < child->tree_x1) {
///cout << "to left\n";
nw->lft = new NodeX(x, x);
nw->lft->gcd = val;
nw->rgh = child;
} else {
///cout << "to right\n";
nw->lft = child;
nw->rgh = new NodeX(x, x);
nw->rgh->gcd = val;
}
nw->gcd = __gcd(nw->lft->gcd, nw->rgh->gcd);
node->rgh = nw;
}
}
setValueX(node->rgh, x, val);
}
ll gcd_lft = 0;
ll gcd_rgh = 0;
if (node->lft) gcd_lft = node->lft->gcd;
if (node->rgh) gcd_rgh = node->rgh->gcd;
node->gcd = __gcd(gcd_lft, gcd_rgh);
}
void setValueY(NodeY* node, int tree_y1, int tree_y2, int y, int x, ll val) {
if (tree_y1 == tree_y2) {
setValueX(node->xRoot, x, val);
return;
}
int tree_mid = (tree_y1 + tree_y2) / 2;
if (y <= tree_mid) {
if (!node->lft) node->lft = new NodeY;
setValueY(node->lft, tree_y1, tree_mid, y, x, val);
} else {
if (!node->rgh) node->rgh = new NodeY;
setValueY(node->rgh, tree_mid + 1, tree_y2, y, x, val);
}
ll gcd_lft = 0;
ll gcd_rgh = 0;
if (node->lft) gcd_lft = queryX(node->lft->xRoot, x, x);
if (node->rgh) gcd_rgh = queryX(node->rgh->xRoot, x, x);
setValueX(node->xRoot, x, __gcd(gcd_lft, gcd_rgh));
}
NodeY* rootY;
void init(int R, int C) {
dimx = R;
dimy = C;
rootY = new NodeY;
}
void update(int P, int Q, long long K) {
int x = P;
int y = Q;
ll k = K;
x++;
y++;
setValueY(rootY, 1, dimy, y, x, k);
}
long long calculate(int P, int Q, int U, int V) {
int x1 = P;
int y1 = Q;
int x2 = U;
int y2 = V;
x1++;
y1++;
x2++;
y2++;
ll sol = queryY(rootY, 1, dimy, y1, y2, x1, x2);
return sol;
}
