#include "game.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd2(ll X, ll Y){
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
struct Treap_Node{
int pri, mn, mx, pos;
ll val, g;
Treap_Node *l, *r;
Treap_Node(){
this->l = this->r = nullptr;
}
Treap_Node(int pos, ll val){
this->l = this->r = nullptr;
this->pri = rng();
this->mn = this->mx = this->pos = pos;
this->val = this->g = val;
}
void update(){
g = val;
mn = mx = pos;
if(l != nullptr){
g = gcd2(g, l->g);
mn = l->mn;
}
if(r != nullptr){
g = gcd2(g, r->g);
mx = r->mx;
}
}
};
struct Treap{
Treap_Node *root;
Treap(){
this->root = nullptr;
}
void split(Treap_Node *n, Treap_Node *&l, Treap_Node *&r, int pos){
if(n == nullptr){
l = r = nullptr;
return;
}
if(n->pos < pos){
split(n->r, n->r, r, pos);
l = n;
}
else{
split(n->l, l, n->l, pos);
r = n;
}
n->update();
}
void merge(Treap_Node *&n, Treap_Node *l, Treap_Node *r){
if(l == nullptr){
n = r;
return;
}
if(r == nullptr){
n = l;
return;
}
if(l->pri < r->pri){
merge(l->r, l->r, r);
n = l;
}
else{
merge(r->l, l, r->l);
n = r;
}
n->update();
}
bool find(int pos){
Treap_Node *n = root;
while(n != nullptr){
if(n->pos == pos){
return true;
}
n = (n->pos < pos ? n->r : n->l);
}
return false;
}
void update(Treap_Node *n, int pos, ll val){
if(n->pos == pos){
n->val = val;
}
else if(n->pos < pos){
update(n->r, pos, val);
}
else{
update(n->l, pos, val);
}
n->update();
}
void insert(int pos, ll val){
if(find(pos)){
update(root, pos, val);
return;
}
Treap_Node *a, *b;
split(root, a, b, pos);
merge(root, a, new Treap_Node(pos, val));
merge(root, root, b);
}
ll query(Treap_Node *n, int u, int v){
if(n != nullptr){
//cout << u << " " << v << " " << n->mx << " " << n->mn << " | " << n->pos << " " << n->val << " " << n->g << endl;
}
if(n == nullptr || n->mx < u || n->mn > v){
return 0;
}
if(u <= n->mn && v >= n->mx){
return n->g;
}
ll ans = gcd2(query(n->l, u, v), query(n->r, u, v));
if(u <= n->pos && v >= n->pos){
ans = gcd2(ans, n->val);
}
return ans;
}
ll query(int u, int v){
return root == nullptr ? 0 : query(root, u, v);
}
};
int cnt_st_node = 0;
struct Segment_Tree{
Treap treap;
Segment_Tree *l, *r;
int low, high;
Segment_Tree(){
this->l = this->r = nullptr;
}
Segment_Tree(int low, int high){
this->l = this->r = nullptr;
this->low = low;
this->high = high;
}
void fix(int pos){
ll val = 0;
if(l != nullptr){
val = gcd2(val, l->treap.query(pos, pos));
}
if(r != nullptr){
val = gcd2(val, r->treap.query(pos, pos));
}
treap.insert(pos, val);
}
void new_left(){
if(l == nullptr){
l = new Segment_Tree(low, (low + high) >> 1);
}
}
void new_right(){
if(r == nullptr){
r = new Segment_Tree(((low + high) >> 1) + 1, high);
}
}
void update(int x, int y, ll val){
if(low == high){
treap.insert(y, val);
return;
}
if(x > ((low + high) >> 1)){
new_right();
r->update(x, y, val);
}
else{
new_left();
l->update(x, y, val);
}
fix(y);
}
ll query(int x, int y, int u, int v){
if(low > u || high < x){
return 0;
}
if(x <= low && u >= high){
return treap.query(y, v);
}
ll g = 0;
if(l != nullptr){
g = gcd2(g, l->query(x, y, u, v));
}
if(r != nullptr){
g = gcd2(g, r->query(x, y, u, v));
}
return g;
}
};
Segment_Tree st;
void init(int R, int C){
st = Segment_Tree(0, R - 1);
}
void update(int P, int Q, ll K){
st.update(P, Q, K);
// cout << " ||| " << endl;
// ll temp = st.query(P, Q, P, Q);
// cout << temp << " ||||| " << endl;
}
ll calculate(int P, int Q, int U, int V){
return st.query(P, Q, U, V);
}
