#include "game.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
struct Treap{
struct Node{
Node *l = nullptr, *r = nullptr;
ll X, Y;
int size = 0;
ll x, s;
Node(ll _X, ll _Y, ll _x){
X = _X, Y = _Y, x = _x, s = x;
}
};
mt19937 rng;
Node* rt = nullptr;
Treap(){
rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
}
int size(Node *nd){ return nd?nd->size:0; }
int size(){ return size(rt); }
void upd_nd(Node *nd){
if(!nd) return;
nd->size = size(nd->l)+size(nd->r)+1;
nd->s = nd->x;
if(nd->l) nd->s = __gcd(nd->s, nd->l->s);
if(nd->r) nd->s = __gcd(nd->s, nd->r->s);
}
pair<Node*, Node*> split(Node* root, ll X){
if(!root) return {nullptr, nullptr};
if(root->X <= X){
auto [L, R] = split(root->r, X);
root->r = L;
upd_nd(root);
return {root, R};
}
else{
auto [L, R] = split(root->l, X);
root->l = R;
upd_nd(root);
return {L, root};
}
}
Node* merge(Node* l, Node* r){
if(!l) return r;
if(!r) return l;
if(l->Y >= r->Y){
l->r = merge(l->r, r);
upd_nd(l);
return l;
}
else{
r->l = merge(l, r->l);
upd_nd(r);
return r;
}
}
Node* search(Node* nd, ll X){
if(!nd) return nullptr;
if(nd->X == X) return nd;
if(nd->X > X) return search(nd->l, X);
return search(nd->r, X);
}
Node* search(ll X){
return search(rt, X);
}
bool search_upd(Node *nd, ll X, ll x){
if(!nd) return 0;
if(nd->X == X){
nd->x = x;
upd_nd(nd);
return 1;
}
if(nd->X > X){
if(search_upd(nd->l, X, x)){
upd_nd(nd);
return 1;
}
return 0;
}
else{
if(search_upd(nd->r, X, x)){
upd_nd(nd);
return 1;
}
return 0;
}
}
bool search_upd(ll X, ll x){
return search_upd(rt, X, x);
}
void insert(ll X, ll x){
auto [L, R] = split(rt, X);
Node* nd = new Node(X, uniform_int_distribution(INT_MIN, INT_MAX)(rng), x);
auto _rt = merge(L, nd);
_rt = merge(_rt, R);
rt = _rt;
}
void update(ll X, ll x){
if(!search_upd(X, x)) insert(X, x);
}
ll get(ll a, ll b){
auto [A, D] = split(rt, a-1);
auto [B, C] = split(D, b);
ll ret = B?B->s:0;
auto _rt = merge(A, B);
_rt = merge(_rt, C);
rt = _rt;
return ret;
}
};
struct sparse_segtree2d{
struct Node2d{
Node2d *l, *r;
Treap sm;
Node2d(){}
Node2d(int m){
l = nullptr, r = nullptr;
}
};
int n, m;
Node2d* root;
sparse_segtree2d(int _n, int _m){
n = _n, m = _m;
root = new Node2d();
}
void upd(Node2d *nd, int l, int r, int a, int b, ll x){
if(l != r){
if(a <= (l+r)/2){
if(!nd->l) nd->l = new Node2d();
upd(nd->l, l, (l+r)/2, a, b, x);
}
else{
if(!nd->r) nd->r = new Node2d();
upd(nd->r, (l+r)/2+1, r, a, b, x);
}
ll sm = 0;
if(nd->l) sm = __gcd(sm, nd->l->sm.get(b, b));
if(nd->r) sm = __gcd(sm, nd->r->sm.get(b, b));
nd->sm.update(b, sm);
}
else nd->sm.update(b, x);
}
void upd(int a, int b, ll x){
upd(root, 0, n-1, a, b, x);
}
ll sum(Node2d* nd, int L, int R, int a1, int b1, int a2, int b2){
if(L > a2 || R < a1) return 0;
if(L >= a1 && R <= a2) return nd->sm.get(b1, b2);
int md = (L+R)/2;
ll rt = 0;
if(nd->l) rt = __gcd(rt, sum(nd->l, L, md, a1, b1, a2, b2));
if(nd->r) rt = __gcd(rt, sum(nd->r, md+1, R, a1, b1, a2, b2));
return rt;
}
ll sum(int a1, int b1, int a2, int b2){
return sum(root, 0, n-1, a1, b1, a2, b2);
}
};
sparse_segtree2d sp(0, 0);
void init(int R, int C){
sp = sparse_segtree2d(R, C);
}
void update(int P, int Q, ll K){
sp.upd(P, Q, K);
}
ll calculate(int P, int Q, int U, int V){
return sp.sum(P, Q, U, V);
}
