#include <bits/stdc++.h>
#include "game.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Node_treap
{
long long init;
long long gcd;
int key;
int prio;
Node_treap *left;
Node_treap *right;
Node_treap (int col, int x)
{
init = x;
gcd = x;
key = col;
prio = rng();
left = nullptr;
right = nullptr;
}
void recalc()
{
gcd = init;
if(left != nullptr) gcd = __gcd(gcd, left->gcd);
if(right != nullptr) gcd = __gcd(gcd, right->gcd);
}
};
struct Node_segtree
{
Node_treap *treap;
Node_segtree *left, *right;
Node_segtree()
{
treap = nullptr;
left = nullptr;
right = nullptr;
}
};
int n, m;
Node_segtree *root = new Node_segtree();
pair<Node_treap*, Node_treap*> split(Node_treap *treap, int x)
{
if(treap == nullptr)
{
return {nullptr, nullptr};
}
if(treap->key <= x)
{
auto [left, right] = split(treap->right, x);
treap->right = left;
treap->recalc();
return {treap, right};
}
else
{
auto [left, right] = split(treap->left, x);
treap->left = right;
treap->recalc();
return {left, treap};
}
}
Node_treap *merge(Node_treap *left, Node_treap *right)
{
if(left == nullptr) return right;
if(right == nullptr) return left;
if(left->prio > right->prio)
{
left->right = merge(left->right, right);
left->recalc();
return left;
}
else
{
right->left = merge(left, right->left);
right->recalc();
return right;
}
}
Node_treap *update_treap(Node_treap *treap, int poz, long long val)
{
auto [left, full_right] = split(treap, poz);
auto [sub, right] = split(full_right, poz + 1);
if(sub != nullptr)
{
delete sub;
}
Node_treap *newNode = new Node_treap(poz, val);
return merge(left, merge(newNode, right));
}
void update_segtree(Node_segtree *node, int left, int right, int pozx, int pozy, long long val)
{
node->treap = update_treap(node->treap, pozy, val);
if(left == right)
{
return;
}
int mij = (left + right) / 2;
if(node->left == nullptr)
{
node->left = new Node_segtree();
}
update_segtree(node->left, left, mij, pozx, pozy, val);
if(node->right == nullptr)
{
node->right = new Node_segtree();
}
update_segtree(node->right, mij+1, right, pozx, pozy, val);
}
long long query_treap(Node_treap *&treap, int st, int dr)
{
auto [left, full_right] = split(treap, st - 1);
auto [sub, right] = split(full_right, dr);
int ans = 0;
if(sub != nullptr)
{
ans = sub->gcd;
}
treap = merge(left, merge(sub, right));
return ans;
}
long long query_segtree(Node_segtree *node, int left, int right, int leftx, int rightx, int lefty, int righty)
{
if(node == nullptr || rightx < left || right < leftx)
{
return 0;
}
if(leftx <= left && right <= rightx)
{
return query_treap(node->treap, lefty, righty);
}
int mij = (left + right) / 2;
return __gcd(query_segtree(node->left, left, mij, leftx, rightx, lefty, righty),
query_segtree(node->right, mij+1, right, leftx, rightx, lefty, righty));
}
void init(int R, int C)
{
n = R;
m = C;
}
void update(int P, int Q, long long K)
{
update_segtree(root, 1, n, P + 1, Q + 1, K + 1);
}
long long calculate(int P, int Q, int U, int V)
{
return query_segtree(root, 1, n, P + 1, Q + 1, U + 1, V + 1);
}
