#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
int64_t gcd2(int64_t x, int64_t y) {
return !y ? x : gcd2(y, x % y);
}
int rnd() {
return ((rand() % (1 << 15)) << 16) + (rand() % (1 << 15));
}
struct tnode_t {
tnode_t *l, *r;
int pos, key, min, max;
int64_t val, g;
tnode_t(int position, int64_t value){
l = nullptr;
r = nullptr;
pos = position;
min = position;
max = position;
key = rnd();
val = value;
g = value;
}
void update(){
g = val;
if(l){
g = gcd2(g, l->g);
}
if(r){
g = gcd2(g, r->g);
}
min = l ? l->min : pos;
max = r ? r->max : pos;
}
};
struct treap_t {
tnode_t *root;
treap_t(){
root = nullptr;
srand(rnd());
}
void split(tnode_t *node, int pos, tnode_t* &l, tnode_t* &r){
if(!node){
l = nullptr;
r = nullptr;
return;
}
if(node->pos < pos){
split(node->r, pos, l, r);
node->r = l;
l = node;
}
else {
split(node->l, pos, l, r);
node->l = r;
r = node;
}
node->update();
}
tnode_t* merge(tnode_t *l, tnode_t *r){
if(!l || !r){
return l ? l : r;
}
if(l->key < r->key){
l->r = merge(l->r, r);
l->update();
return l;
}
r->l = merge(l, r->l);
r->update();
return r;
}
bool find(int pos){
tnode_t* node = root;
while(node){
if(node->pos == pos){
return true;
}
if(node->pos > pos){
node = node->l;
}
else {
node = node->r;
}
}
return false;
}
void update(tnode_t *node, int pos, int64_t val){
if(node->pos == pos){
node->val = val;
node->update();
return;
}
if(node->pos > pos){
update(node->l, pos, val);
}
else {
update(node->r, pos, val);
}
node->update();
}
void insert(int pos, int64_t val){
if(find(pos)){
update(root, pos, val);
return;
}
tnode_t *l = nullptr, *r = nullptr;
split(root, pos, l, r);
tnode_t *merged_left = merge(l, new tnode_t(pos, val));
root = merge(merged_left, r);
}
int64_t query(tnode_t *node, int left, int right){
if(node->max < left || node->min > right){
return 0;
}
if(left <= node->min && node->max <= right){
return node->g;
}
int64_t res = (left <= node->pos && node->pos <= right) ? node->val : 0;
if(node->l){
res = gcd2(res, query(node->l, left, right));
}
if(node->r){
res = gcd2(res, query(node->r, left, right));
}
return res;
}
int64_t query(int left, int right){
if(!root){
return 0;
}
return query(root, left, right);
}
};
struct snode_t {
snode_t *l, *r;
treap_t treap;
int left, right;
snode_t(){
l = nullptr;
r = nullptr;
}
snode_t(int left_bound, int right_bound){
l = nullptr;
r = nullptr;
left = left_bound;
right = right_bound;
}
void add_left(){
if(!l){
l = new snode_t(left, (left + right) / 2);
}
}
void add_right(){
if(!r){
r = new snode_t((left + right) / 2 + 1, right);
}
}
void fix(int pos){
int64_t val = 0;
if(l){
val = gcd2(val, l->treap.query(pos, pos));
}
if(r){
val = gcd2(val, r->treap.query(pos, pos));
}
treap.insert(pos, val);
}
void update(int row, int col, int64_t val){
if(right < row || row < left){
return;
}
if(left == right){
treap.insert(col, val);
return;
}
if(row <= (left + right) / 2){
add_left();
l->update(row, col, val);
}
else {
add_right();
r->update(row, col, val);
}
fix(col);
}
int64_t query(int row0, int row1, int col0, int col1){
if(row0 > right || row1 < left){
return 0;
}
if(row0 <= left && right <= row1){
return treap.query(col0, col1);
}
int64_t res = 0;
if(l){
res = gcd2(res, l->query(row0, row1, col0, col1));
}
if(r){
res = gcd2(res, r->query(row0, row1, col0, col1));
}
return res;
}
};
snode_t tree;
void init(int row_count, int col_count) {
srand(12341234);
tree = snode_t(0, row_count);
}
void update(int row, int col, long long val) {
tree.update(row, col, val);
}
long long calculate(int row0, int col0, int row1, int col1) {
return tree.query(row0, row1, col0, col1);
}
