#include <bits/stdc++.h>
#include "game.h"
using namespace std;
struct Node {
Node* left;
Node* right;
long long x, y;
long long val1, val2;
Node (long long x, long long val) {
this->x = x, this->y = rand(), this->left = nullptr, this->right = nullptr, this->val1 = this->val2 = val;
}
};
long long gcd (long long a, long long b) {
return a + b;
}
void print (Node*x) {
if (x != nullptr) {
print(x->left);
print(x->right);
}
}
long long g (Node*x) {
return ((x == nullptr) ? 0 : x->val2);
}
void upd (Node*&x) {
x->val2 = gcd(gcd(g(x->left), g(x->right)), x->val1);
}
pair<Node*, Node*> splitX (Node*cur, long long x) {
if (cur == nullptr) return make_pair(nullptr, nullptr);
if (cur->right == nullptr && cur->x <= x) {
return make_pair(cur, nullptr);
}
if (cur->left == nullptr && cur->x > x) {
return make_pair(nullptr, cur);
}
if (cur->x <= x) {
auto p = splitX(cur->right, x);
cur->right = p.first;
upd(cur);
return make_pair(cur, p.second);
} else {
auto p = splitX(cur->left, x);
cur->left = p.second;
upd(cur);
return make_pair(p.first, cur);
}
}
Node* merge (Node* node1, Node* node2) {
if (node1 == nullptr) return node2;
if (node2 == nullptr) return node1;
if (node2->y <= node1->y) {
node2->left = merge(node1, node2->left);
upd(node2);
return node2;
} else {
node1->right = merge(node1->right, node2);
upd(node1);
return node1;
}
}
int64_t query (Node* root, int l, int r) {
auto p = splitX(root, l - 1); //[<= l - 1, >= l]
auto q = splitX(p.second, r); //[>= l <= r, >r]
long long ans = g(q.first);
return ans;
}
void update (Node*& root, int x, long long val) {
//update the thing at index x to be val
auto p = splitX(root, x - 1);
auto q = splitX(p.second, x);
root = merge(p.first, merge(new Node(x, val), q.second));
}
map<int,Node*> myMap;
Node*root;
void update (int x, int y, long long z) {
Node*cur = myMap[x];
update(cur, y, z);
myMap[x] = cur;
}
long long calculate (int x1, int y1, int x2, int y2) {
long long ans = 0;
for (int x = x1; x <= x2; x++) {
if (!myMap.count(x)) continue;
ans = gcd(ans, query(myMap[x], y1, y2));
}
return ans;
}
void init (int n, int m) {
}
/*
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
init(n, m);
update(0, 0, 100);
cout << calculate(0, 0, 0, 1) << '\n';
/*
int q;
cin >> q;
while (q--) {
int t;
cin >> t;
if (t == 1) {
//update
int x, y, z;
cin >> x >> y >> z;
Node*cur = myMap[x];
update(cur, y, z);
myMap[x] = cur;
assert(myMap.count(0));
} else {
//query
int x1, x2, y1, y2;
cin >> x1 >> x2 >> y1 >> y2;
int ans = 0;
for (int x = x1; x <= x2; x++) {
if (!myMap.count(x)) continue;
ans = gcd(ans, query(myMap[x], y1, y2));
}
cout << ans << '\n';
}
}
}
*/
