#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e9+5;
int n, m;
ll gcd(ll a, ll b) {
if (a == 0) return b;
return gcd(b%a, a);
}
struct Node {
ll val;
Node *l, *r;
Node() {
val = 0;
l = r = NULL;
}
void addSide() {
if (l == NULL) {
l = new Node();
r = new Node();
}
}
};
struct SegTree {
Node *tree;
SegTree *l, *r;
SegTree() {
tree = new Node();
l = r = NULL;
}
void addSide() {
if (l == NULL) {
l = new SegTree();
r = new SegTree();
}
}
void update(int l, int r, int id, ll val, Node *head) {
if (l == r) {
head->val = val;
return;
}
int mid = (l+r)>>1;
// head->addSide();
if (id <= mid && !head->l) head->l = new Node();
else if (mid < id && !head->r) head->r = new Node();
if (id <= mid) update(l, mid, id, val, head->l);
else update(mid+1, r, id, val, head->r);
head->val = gcd((head->l ? head->l->val : 0ll), (head->r ? head->r->val : 0ll));
}
ll query(int l, int r, int L, int R, Node *head) {
if (l > R || L > r || !head) return 0;
if (L <= l && r <= R) return head->val;
int mid = (l+r)>>1;
return gcd(
query(l, mid, L, R, head->l),
query(mid+1, r, L, R, head->r)
);
}
void update1D(int pos, ll val) {
update(1, m, pos, val, tree);
}
ll query1D(int l, int r) {
return query(1, m, l, r, tree);
}
ll query1D(int l) {
return query(1, m, l, l, tree);
}
} *root;
void update2D(int l, int r, int a, int b, ll val, SegTree *head) {
if (l == r) {
head->update1D(b, val);
return;
}
int mid = (l+r)>>1;
// head->addSide();
if (a <= mid && !head->l) head->l = new SegTree();
else if (mid < a && !head->r) head->r = new SegTree();
if (a <= mid) update2D(l, mid, a, b, val, head->l);
else update2D(mid+1, r, a, b, val, head->r);
head->update1D(
b,
gcd(
(head->l ? head->l->query1D(b) : 0),
(head->r ? head->r->query1D(b) : 0)
)
);
}
ll query2D(int l, int r, int l1, int r1, int l2, int r2, SegTree *head) {
if (l1 > r || l > r1 || !head) return 0;
if (l1 <= l && r <= r1) return head->query1D(l2, r2);
int mid = (l+r)>>1;
return gcd(
query2D(l, mid, l1, r1, l2, r2, head->l),
query2D(mid+1, r, l1, r1, l2, r2, head->r)
);
}
void init(int _n, int _m) {
n = _n;
m = _m;
root = new SegTree();
}
void update(int a, int b, ll val) {
update2D(1, n, a+1, b+1, val, root);
}
ll calculate(int l1, int l2, int r1, int r2) {
return query2D(1, n, l1+1, r1+1, l2+1, r2+1, root);
}
