#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;
}
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;
}
struct cnode_t;
struct rnode_t;
deque<cnode_t> cnodes;
deque<rnode_t> rnodes;
cnode_t* fetch_cnode(){
cnodes.emplace_back();
return &cnodes.back();
}
rnode_t* fetch_rnode(){
rnodes.emplace_back();
return &rnodes.back();
}
// column node
struct cnode_t {
int64_t val = 0;
cnode_t* left = nullptr;
cnode_t* right = nullptr;
void expand(p32 range, p32 dest){
if(range.second - range.first == 1){
return;
}
int mid = (range.first + range.second) / 2;
if(!left && ranges({range.first, mid}, dest)){
left = fetch_cnode();
}
if(!right && ranges({mid, range.second}, dest)){
right = fetch_cnode();
}
}
};
// row node
struct rnode_t {
cnode_t* col = nullptr;
rnode_t* left = nullptr;
rnode_t* right = nullptr;
rnode_t(){
col = fetch_cnode();
}
void expand(p32 range, p32 dest){
if(range.second - range.first == 1){
return;
}
int mid = (range.first + range.second) / 2;
if(!left && ranges({range.first, mid}, dest)){
left = fetch_rnode();
}
if(!right && ranges({mid, range.second}, dest)){
right = fetch_rnode();
}
}
};
rnode_t* tree;
p32 __row_range;
p32 __col_range;
int64_t get_val(cnode_t *node){
if(!node){
return 0;
}
return gcd2((node->left) ? node->left->val : 0,
(node->right) ? node->right->val : 0);
}
int64_t get_val(cnode_t *left, cnode_t *right){
return gcd2((left) ? left->val : 0,
(right) ? right->val : 0);
}
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, dest);
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 = get_val(node);
}
void update_merge(cnode_t *node, cnode_t *left, cnode_t *right, p32 range, p32 dest){
if(!node){
return;
}
int type = ranges(range, dest);
if(!type){
return;
}
if(type == 1){
node->val = get_val(left, right);
return;
}
node->expand(range, dest);
if(left){
left->expand(range, dest);
}
if(right){
right->expand(range, dest);
}
int mid = (range.first + range.second) / 2;
update_merge(node->left,
(left) ? left->left : nullptr,
(right) ? right->left : nullptr,
{range.first, mid}, dest);
update_merge(node->right,
(left) ? left->right : nullptr,
(right) ? right->right : nullptr,
{mid, range.second}, dest);
node->val = get_val(left, right);
}
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, dest);
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) ? node->left->col : nullptr,
(node->right) ? node->right->col : nullptr,
__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;
}
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);
}
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 = fetch_rnode();
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) {
// ciuj taip reik:
// * perskaiciuot tame specifiniame medyje gcd (tos eilutes)
// * perskaiciuot visu eiluciu gabalu reiksmes
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});
}
