#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;
const int lim1 = 22000*35, lim2 = 22000*35;
struct Node{
Node *l = nullptr, *r = nullptr;
int X, Y;
ll x, s;
Node(){}
Node(int _X, int _Y, ll _x){
X = _X, Y = _Y, x = _x, s = x;
}
};
Node T1[lim1];
int cnt1 = 0;
Node* newNode(int X, int Y, ll x){
T1[cnt1] = Node(X, Y, x);
return &T1[cnt1++];
}
namespace Treap{
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void upd_nd(Node *nd){
if(!nd) return;
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, int 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;
}
}
bool search_upd(Node *nd, int 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;
}
}
void insert(Node *&rt, int X, ll x){
auto [L, R] = split(rt, X);
Node* nd = newNode(X, uniform_int_distribution(INT_MIN, INT_MAX)(rng), x);
auto _rt = merge(L, nd);
_rt = merge(_rt, R);
rt = _rt;
}
void update(Node *&root, int X, ll x){
if(!search_upd(root, X, x)) insert(root, X, x);
}
ll get(Node* nd, int X){
if(!nd) return 0;
if(nd->X == X) return nd->x;
if(nd->X > X) return get(nd->l, X);
return get(nd->r, X);
}
ll get(Node *& rt, int a, int 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 Node2d{
Node2d *l = nullptr, *r = nullptr;
Node* tp = nullptr;
Node2d(){}
};
Node2d T2[lim2];
int cnt2 = 0;
Node2d* newNode2d(){
return &T2[cnt2++];
}
struct sparse_segtree2d{
int n, m;
Node2d* root;
sparse_segtree2d(int _n, int _m){
n = _n, m = _m;
root = newNode2d();
}
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 = newNode2d();
upd(nd->l, l, (l+r)/2, a, b, x);
}
else{
if(!nd->r) nd->r = newNode2d();
upd(nd->r, (l+r)/2+1, r, a, b, x);
}
ll s = 0;
if(nd->l) s = __gcd(s, Treap::get(nd->l->tp, b));
if(nd->r) s = __gcd(s, Treap::get(nd->r->tp, b));
Treap::update(nd->tp, b, s);
}
else Treap::update(nd->tp, b, x);
}
void upd(int a, int b, ll x){
upd(root, 0, n-1, a, b, x);
}
ll get(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 Treap::get(nd->tp, b1, b2);
int md = (L+R)/2;
ll rt = 0;
if(nd->l) rt = __gcd(rt, get(nd->l, L, md, a1, b1, a2, b2));
if(nd->r) rt = __gcd(rt, get(nd->r, md+1, R, a1, b1, a2, b2));
return rt;
}
ll get(int a1, int b1, int a2, int b2){
return get(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.get(P, Q, U, V);
}
