#include "game.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll a, ll b) {return a + rng() % (b - a + 1);}
int n, m;
struct node {
node *left, *right;
ll val;
};
ll gcd(ll a, ll b, ll c) {
return __gcd(__gcd(a, b), c);
}
struct Treap {
struct node {
node *l, *r;
ll x, y;
ll gc, val;
node(ll X) {
l = r = NULL;
x = X, y = rand(1, (ll)1e9);
}
};
node *root = 0;
ll get(node *a) {
if(a == NULL) return 0;
return a->gc;
}
void split(node *t, node *&l, node *&r, int k) {
if(!t) {
l = r = NULL;
} else if(t->x <= k) {
split(t->r, t->r, r, k), l = t;
} else {
split(t->l, l, t->l, k), r = t;
}
if(t != NULL)
t->gc = gcd(get(t->l), get(t->r), t->val);
}
void merge(node *&t, node *l, node *r) {
if(!l) {
t = r;
} else if(!r) {
t = l;
} else if(l->y > r->y) {
merge(l->r, l->r, r), t = l;
} else {
merge(r->l, l, r->l), t = r;
}
if(t != NULL)
t->gc = gcd(get(t->l), get(t->r), t->val);
}
bool find(node* t, ll k) {
if(t == NULL) return false;
if(t->x == k) return true;
if(t->x > k) return find(t->l, k);
else return find(t->r, k);
}
ll query(int l, int r) {
if(root == NULL) return 0;
node *A, *B, *C;
split(root, A, B, l - 1);
split(B, B, C, r);
ll ans = (B == NULL ? 0 : B->gc);
merge(root, A, B);
merge(root, root, C);
return ans;
}
void modif(int j, ll val) {
node *A, *B, *C;
if(find(root, j)) {
split(root, A, B, j - 1);
split(B, B, C, j);
B->val = val;
merge(root, A, B);
merge(root, root, C);
} else {
split(root, A, B, j - 1);
C = new node(j);
C->val = val;
merge(root, A, C);
merge(root, root, B);
}
}
};
struct purice {
purice *left, *right;
Treap paiu;
};
void modifi(purice *&i, int l, int r, int posi, int posj, ll val) {
if(l > posi || r < posi) return;
if(!i) i = new purice();
if(l == posi && r == posi) {
i->paiu.modif(posj, val);
return;
}
int mid = (l + r) >> 1;
modifi(i->left, l, mid, posi, posj, val);
modifi(i->right, mid + 1, r, posi, posj, val);
ll leftval = 0, rightval = 0;
if(i->left) leftval = i->left->paiu.query(posj, posj);
if(i->right) rightval = i->right->paiu.query(posj, posj);
ll new_val = __gcd(leftval, rightval);
i->paiu.modif(posj, new_val);
}
ll queryi(purice* i, int l, int r, int tli, int tri, int tlj, int trj) {
if(l > tri || r < tli) return 0;
if(!i || l > tri || r < tli) return 0;
if(l >= tli && r <= tri) return i->paiu.query(tlj, trj);
int mid = (l + r) >> 1;
return __gcd(queryi(i->left, l, mid, tli, tri, tlj, trj), queryi(i->right, mid + 1, r, tli, tri, tlj, trj));
}
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
purice *amogus;
void init(int R, int C) {
n = R, m = C;
}
void update(int P, int Q, long long K) {
modifi(amogus, 0, n - 1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return queryi(amogus, 0, n - 1, P, U, Q, V);
}
