#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int n , m;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void init(int _n , int _m){
n = _n;
m = _m;
srand(time(NULL));
}
struct Node{
Node *left , *right;
int pos;
long long val , gcd_sum , prio;
Node(){};
Node(int _pos , long long _val){
left = right = nullptr;
pos = _pos;
val = gcd_sum = _val;
prio = rng();
}
};
struct Treap{
Node *root;
Treap(){
root = nullptr;
}
void Delete(Node *&root){
if (root == nullptr) return;
Delete(root->left);
Delete(root->right);
delete root;
root = nullptr;
}
void ClearAll(){
Delete(root);
}
~Treap(){
ClearAll();
}
long long GetGcd(Node *root){
if (root == nullptr) return 0; else return root->gcd_sum;
}
void Merge(Node *&root , Node *left , Node *right){
if (left == nullptr){
root = right;
return;
}
if (right == nullptr){
root = left;
return;
}
if (left->prio < right->prio){
Merge(left->right , left->right , right);
root = left;
}
else{
Merge(right->left , left , right->left);
root = right;
}
root->gcd_sum = __gcd(root->val , __gcd(GetGcd(root->left) , GetGcd(root->right)));
}
void Split(Node *root , Node *&left , Node *&right , int pos){
if (root == nullptr){
left = right = nullptr;
return;
}
if (root->pos < pos){
Split(root->right , root->right , right , pos);
left = root;
}
else{
Split(root->left , left , root->left , pos);
right = root;
}
root->gcd_sum = __gcd(root->val , __gcd(GetGcd(root->left) , GetGcd(root->right)));
}
void Update(int pos , long long val){
Node *A , *B , *C , *D;
A = B = C = D = nullptr;
Split(root , A , B , pos);
Split(B , C , D , pos + 1);
delete C;
C = new Node(pos , val);
Merge(root , A , C);
Merge(root , root , D);
}
long long GetRange(int l , int r){
Node *A , *B , *C , *D;
A = B = C = D = nullptr;
Split(root , A , B , l);
Split(B , C , D , r + 1);
long long ans = GetGcd(C);
Merge(root , A , C);
Merge(root , root , D);
return ans;
}
};
struct Node2{
Treap T;
Node2 *left , *right;
Node2(){
T = Treap();
left = right = nullptr;
};
};
struct SegmentTree{
Node2 *root;
SegmentTree(){
root = new Node2();
}
void Delete(Node2 *&root){
if (root == nullptr) return;
Delete(root->left);
Delete(root->right);
(root->T).ClearAll();
}
void ClearAll(){
Delete(root);
}
~SegmentTree(){
ClearAll();
}
void Update(Node2 *root , int l , int r , int x , int y , long long val){
if (l == r){
root->T.Update(y , val);
return;
}
int mid = (l + r) / 2;
if (x <= mid){
if (root->left == nullptr) root->left = new Node2();
Update(root->left , l , mid , x , y , val);
}
else{
if (root->right == nullptr) root->right = new Node2();
Update(root->right , mid + 1 , r , x , y , val);
}
long long left_gcd = (root->left == nullptr) ? 0 : (root->left->T).GetRange(y , y);
long long right_gcd = (root->right == nullptr) ? 0 : (root->right->T).GetRange(y , y);
long long combine_gcd = __gcd(left_gcd , right_gcd);
root->T.Update(y , combine_gcd);
}
long long Get(Node2 *root , int l , int r , int x , int y , int u , int v){
if (u < l || r < x) return 0;
if (x <= l && r <= u) return (root->T).GetRange(y , v);
int mid = (l + r) / 2;
long long left_gcd = (root->left == nullptr) ? 0 : Get(root->left , l , mid , x , y , u , v);
long long right_gcd = (root->right == nullptr) ? 0 : Get(root->right , mid + 1 , r , x , y , u , v);
return __gcd(left_gcd , right_gcd);
}
} S;
void update(int x , int y , long long val){
S.Update(S.root , 0 , n - 1 , x , y , val);
}
long long calculate(int x , int y , int u , int v){
return S.Get(S.root , 0 , n - 1 , x , y , u , v);
}
