#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int r, c;
struct NodeCol{
NodeCol *left, *right;
long long answer;
NodeCol(){
left = right = nullptr;
answer = 0;
}
};
struct NodeRow{
NodeRow *left, *right;
NodeCol *col;
NodeRow(){
left = right = nullptr;
col = nullptr;
}
};
struct DynamicSegmentTree2D{
NodeRow *root = new NodeRow();
void update_col(NodeCol *cur, NodeRow *cur_row, int start, int end,
int col_id, int row_start, int row_end, long long value){
if(start == end){
if(row_start == row_end){
cur->answer = value;
}else{
long long left_val = 0, right_val = 0;
if(cur_row->left && cur_row->left->col)
left_val = cur_row->left->col->answer;
if(cur_row->right && cur_row->right->col)
right_val = cur_row->right->col->answer;
cur->answer = __gcd(left_val, right_val);
}
return;
}
int mid = (start + end) / 2;
if(col_id <= mid){
if(cur->left == nullptr) cur->left = new NodeCol();
update_col(cur->left, cur_row, start, mid, col_id, row_start, row_end, value);
}else{
if(cur->right == nullptr) cur->right = new NodeCol();
update_col(cur->right, cur_row, mid+1, end, col_id, row_start, row_end, value);
}
long long left_val = cur->left ? cur->left->answer : 0;
long long right_val = cur->right ? cur->right->answer : 0;
cur->answer = __gcd(left_val, right_val);
}
void update_row(NodeRow *cur, int start, int end,
int row_id, int col_id, long long value){
if(start != end){
int mid = (start + end) / 2;
if(row_id <= mid){
if(cur->left == nullptr) cur->left = new NodeRow();
update_row(cur->left, start, mid, row_id, col_id, value);
}else{
if(cur->right == nullptr) cur->right = new NodeRow();
update_row(cur->right, mid+1, end, row_id, col_id, value);
}
}
if(cur->col == nullptr) cur->col = new NodeCol();
update_col(cur->col, cur, 0, c - 1, col_id, start, end, value);
}
long long query_col(NodeCol *cur, int start, int end, int l, int r){
if(!cur || start > r || end < l) return 0;
if(l <= start && end <= r)
return cur->answer;
int mid = (start + end) / 2;
return __gcd(
query_col(cur->left, start, mid, l, r),
query_col(cur->right, mid+1, end, l, r)
);
}
long long query_row(NodeRow *cur, int start, int end,
int l, int r, int col_l, int col_r){
if(!cur || start > r || end < l) return 0;
if(l <= start && end <= r)
return query_col(cur->col, 0, c - 1, col_l, col_r);
int mid = (start + end) / 2;
return __gcd(
query_row(cur->left, start, mid, l, r, col_l, col_r),
query_row(cur->right, mid+1, end, l, r, col_l, col_r)
);
}
void update(int r1, int c1, long long value){
update_row(root, 0, r - 1, r1, c1, value);
}
long long query(int r1, int c1, int r2, int c2){
return query_row(root, 0, r - 1, r1, r2, c1, c2);
}
} tr;
void init(int R, int C){
r = R;
c = C;
}
void update(int P, int Q, long long K){
tr.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V){
return tr.query(P, Q, U, V);
}
