#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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;
}
mt19937_64 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
struct Treap{
struct Node{
Node *lnode, *rnode;
ll val, gg, h;
int pos;
Node(int pos, ll x):val(x),gg(x),h(ayahya()),pos(pos),lnode(nullptr),rnode(nullptr){}
} *root;
Treap():root(nullptr){}
void upd(Node* nd){
nd->gg=nd->val;
if (nd->lnode) nd->gg=gcd2(nd->lnode->gg,nd->gg);
if (nd->rnode) nd->gg=gcd2(nd->rnode->gg,nd->gg);
}
Node* merge(Node* a, Node* b){
if (!a || !b) return (a?a:b);
if (a->h > b->h) return a->rnode = merge(a->rnode,b),upd(a),a;
return b->lnode = merge(a,b->lnode),upd(b),b;
}
pair<Node*, Node*> split(Node* node, int x){
if (!node) return {nullptr,nullptr};
if (node->pos>=x){
pair<Node*, Node*> spl = split(node->lnode,x);
node->lnode=spl.second;
upd(node);
return {spl.first,node};
}
pair<Node*, Node*> spl = split(node->rnode,x);
node->rnode=spl.first;
upd(node);
return {node,spl.second};
}
void update(int x, ll val){
if (root==nullptr){
return root = new Node(x,val), void(23);
}
Node* nd = root;
while (nd){
if (nd->pos==x) break;
if (nd->pos>x) nd=nd->lnode;
else nd=nd->rnode;
}
if (nd==nullptr){
Node* nnode = new Node(x,val);
pair<Node*, Node*> spl = split(root,x);
root=merge(spl.first,nnode);
root=merge(root,spl.second);
}
else {
vector<Node*> backtrack;
nd->val=val;
upd(nd);
nd = root;
while (nd->pos!=x){
backtrack.push_back(nd);
if (nd->pos>x) nd=nd->lnode;
else nd=nd->rnode;
}
while (backtrack.size()){
upd(backtrack.back());
backtrack.pop_back();
}
}
}
ll queri(int x){
Node* nd = root;
while (nd!=nullptr){
if (nd->pos==x) return nd->val;
if (nd->pos>x) nd=nd->lnode;
else nd=nd->rnode;
}
return 0;
}
ll query(int l, int r){
pair<Node*, Node*> spl = split(root, l);
pair<Node*, Node*> spl2 = split(spl.second, r+1);
ll ret = 0;
if (spl2.first) ret = spl2.first->gg;
root = merge(spl2.first,spl2.second);
root = merge(spl.first,root);
return ret;
}
};
constexpr int MAXN = 1000000000;
struct SegTree{
struct Node{
Node *lnode, *rnode;
Treap tr;
Node():lnode(nullptr),rnode(nullptr){}
} *root;
SegTree():root(new Node){}
void update(int x, int y, ll val, int l = 0, int r = MAXN, Node* nd = nullptr){
if (l==0 && r==MAXN) nd=root;
if (l==r){
return nd->tr.update(y,val);
}
int mid = l+(r-l)/2;
if (mid>=x){
if (nd->lnode==nullptr) nd->lnode=new Node;
update(x,y,val,l,mid,nd->lnode);
}
else {
if (nd->rnode==nullptr) nd->rnode=new Node;
update(x,y,val,mid+1,r,nd->rnode);
}
ll ret = 0;
if (nd->lnode) ret=nd->lnode->tr.queri(y);
if (nd->rnode) ret=gcd2(nd->rnode->tr.queri(y),ret);
nd->tr.update(y,ret);
}
ll query(int tl, int tr, int a, int b, int l = 0, int r = MAXN, Node* node = nullptr){
if (l==0 && r==MAXN) node=root;
if (l>=tl && r<=tr) return node->tr.query(a,b);
if (l>tr || r<tl) return 0;
int mid = l+(r-l)/2;
ll ret = 0;
if (node->lnode && mid>=tl) ret=gcd2(ret,query(tl,tr,a,b,l,mid,node->lnode));
if (node->rnode && mid<tr) ret=gcd2(ret,query(tl,tr,a,b,mid+1,r,node->rnode));
return ret;
}
} segtree;
void init(int R, int C) {
//23 severim
}
void update(int P, int Q, long long K) {
segtree.update(P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return segtree.query(P,U,Q,V);
}
