#include "game.h"
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <vector>
#include <fstream>
#include <bitset>
#include <tuple>
#include <cmath>
#include <cstdint>
#include <stack>
#include <cassert>
#include <cstdio>
#include <queue>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <sstream>
const int MAX_C = 100000;
const int MAX_R = 100;
int r, c;
using namespace std;
#define int long long
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 {
node* left, * right;
int gcd;
void updates() {
gcd = gcd2(left->gcd, right->gcd);
}
};
vector<node*> roots;
node* ori_root;
int query_ver(node* root, int left, int right, int qLeft, int qRight) {
if (left > qRight || right < qLeft) return 0;
if (left >= qLeft && right <= qRight) return root->gcd;
int mid = (left + right) / 2;
return gcd2(query_ver(root->left, left, mid, qLeft, qRight), query_ver(root->right, mid + 1, right, qLeft, qRight));
}
void update_ver(node* root, int left, int right, int point, int nValue) {
int qLeft, qRight;
qLeft = qRight = point;
if (left > qRight || right < qLeft) return;
if (left >= qLeft && right <= qRight) {
root->gcd = nValue;
return;
}
int mid = (left + right) / 2;
update_ver(root->left, left, mid, point, nValue);
update_ver(root->right, mid + 1, right, point, nValue);
root->updates();
}
void build_ver(node* root, int left, int right) {
if (left == right) {
root->gcd = 0;
return;
}
int mid = (left + right) / 2;
root->left = new node{ NULL, NULL, 0 };
root->right = new node{ NULL, NULL, 0 };
build_ver(root->left, left, mid);
build_ver(root->right, mid + 1, right);
root->updates();
}
int query_hor(node* root, int left, int right, int qLeft, int qRight, int qDown, int qUp) {
if (left > qRight || right < qLeft) return 0;
if (left == right) {
return query_ver(root, 0, r-1, qDown, qUp);
}
int mid = (left + right) / 2;
return gcd2(query_hor(root->left, left, mid, qLeft, qRight, qDown, qUp), query_hor(root->right, mid + 1, right, qLeft, qRight, qDown, qUp));
}
void update_hor(node* root, int left, int right, int hor_point, int ver_point, int nValue) {
int qLeft, qRight;
qLeft = qRight = hor_point;
if (left > qRight || right < qLeft) return;
if (left == right) {
update_ver(root, 0, r - 1, ver_point, nValue);
return;
}
int mid = (left + right) / 2;
update_hor(root->left, left, mid, hor_point, ver_point, nValue);
update_hor(root->right, mid + 1, right, hor_point, ver_point, nValue);
root->updates();
}
void build_hor(node* root, int left, int right) {
if (left == right) {
build_ver(root, 0, r-1);
return;
}
int mid = (left + right) / 2;
root->left = new node{ NULL, NULL, 0 };
root->right = new node{ NULL, NULL, 0 };
build_hor(root->left, left, mid);
build_hor(root->right, mid + 1, right);
root->updates();
}
void destroy(node* root) {
if (root->left) destroy(root->left);
if (root->right) destroy(root->right);
delete root;
}
void init(signed R, signed C) {
r = R;
c = C;
ori_root = new node{ NULL,NULL,0 };
build_hor(ori_root, 0, C - 1);
return;
}
void update(signed P, signed Q, long long K) {
update_hor(ori_root, 0, c - 1, Q, P, K);
}
long long calculate(signed P, signed Q, signed U, signed V) {
int gcd = 0;
gcd = query_hor(ori_root, 0, c - 1, Q, V, P, U);
return gcd;
}
