#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
#pragma endregion
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;
}
// column node
struct cnode_t {
int64_t val = 0;
cnode_t* left = nullptr;
cnode_t* right = nullptr;
void expand(p32 range){
if(range.second - range.first == 1){
return;
}
left = (left) ? left : new cnode_t;
right = (right) ? right : new cnode_t;
}
};
// row node
struct rnode_t {
cnode_t* col = nullptr;
rnode_t* left = nullptr;
rnode_t* right = nullptr;
rnode_t(){
col = new cnode_t();
}
void expand(p32 range){
if(range.second - range.first == 1){
return;
}
left = (left) ? left : new rnode_t;
right = (right) ? right : new rnode_t;
}
};
rnode_t* tree;
p32 __row_range;
p32 __col_range;
int ranges(p32 a, p32 b){
if(a.first >= b.second || a.second <= b.first){
return 0;
}
if(a.first >= b.first && a.second <= b.second){
return 1;
}
return 2;
}
void update_base(cnode_t *node, int64_t val, p32 range, p32 dest){
if(!node){
return;
}
int type = ranges(range, dest);
if(!type){
return;
}
if(type == 1){
node->val = val;
return;
}
node->expand(range);
int mid = (range.first + range.second) / 2;
update_base(node->left, val, {range.first, mid}, dest);
update_base(node->right, val, {mid, range.second}, dest);
node->val = gcd2(node->left->val, node->right->val);
}
void update_merge(cnode_t *node, cnode_t *left, cnode_t *right, p32 range, p32 dest){
if(!node || !left || !right){
return;
}
int type = ranges(range, dest);
if(!type){
return;
}
if(type == 1){
node->val = gcd2(left->val, right->val);
return;
}
node->expand(range);
left->expand(range);
right->expand(range);
int mid = (range.first + range.second) / 2;
update_merge(node->left, left->left, right->left, {range.first, mid}, dest);
update_merge(node->right, left->right, right->right, {mid, range.second}, dest);
node->val = gcd2(node->left->val, node->right->val);
}
void update_row(rnode_t *node, int64_t val, p32 range, p32 dest, p32 col_dest){
if(!node){
return;
}
int type = ranges(range, dest);
if(!type){
return;
}
if(type == 1){
update_base(node->col, val, __col_range, col_dest);
return;
}
node->expand(range);
int mid = (range.first + range.second) / 2;
update_row(node->left, val, {range.first, mid}, dest, col_dest);
update_row(node->right, val, {mid, range.second}, dest, col_dest);
update_merge(node->col, node->left->col, node->right->col, __col_range, col_dest);
}
int64_t query_col(cnode_t *node, p32 range, p32 dest){
if(!node){
return 0;
}
int type = ranges(range, dest);
if(!type){
return 0;
}
if(type == 1){
return node->val;
}
node->expand(range);
int mid = (range.first + range.second) / 2;
int64_t left = query_col(node->left, {range.first, mid}, dest);
int64_t right = query_col(node->right, {mid, range.second}, dest);
return gcd2(left, right);
}
int64_t query_row(rnode_t *node, p32 range, p32 dest, p32 col_dest){
if(!node){
return 0;
}
int type = ranges(range, dest);
if(!type){
return 0;
}
if(type == 1){
return query_col(node->col, __col_range, col_dest);
}
node->expand(range);
int mid = (range.first + range.second) / 2;
int64_t left = query_row(node->left, {range.first, mid}, dest, col_dest);
int64_t right = query_row(node->right, {mid, range.second}, dest, col_dest);
return gcd2(left, right);
}
void init(int row_count, int col_count) {
tree = new rnode_t;
row_count = 1 << int(log2(row_count) + 1);
col_count = 1 << int(log2(col_count) + 1);
__row_range = {0, row_count};
__col_range = {0, col_count};
}
void update(int row, int col, long long val) {
update_row(tree, (int64_t)val, __row_range, {row, row + 1}, {col, col + 1});
}
long long calculate(int row0, int col0, int row1, int col1) {
return query_row(tree, __row_range, {row0, row1 + 1}, {col0, col1 + 1});
}
