#include "game.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int n, m;
struct node {
node *left, *right;
ll val;
};
void modifj(node *&i, int l, int r, int pos, ll val) {
if(l > pos || r < pos) return;
if(!i) {
i = new node();
i-> val = 0;
}
if(l == pos && r == pos) {
i->val = val;
return;
}
int mid = (l + r) >> 1;
modifj(i->left, l, mid, pos, val);
modifj(i->right, mid + 1, r, pos, val);
ll leftval = 0, rightval = 0;
if(i->left) leftval = i->left->val;
if(i->right) rightval = i->right->val;
i->val = __gcd(leftval, rightval);
}
ll queryj(node* i, int l, int r, int tl, int tr) {
if(!i || l > tr || r < tl) return 0;
if(l >= tl && r <= tr) return i->val;
int mid = (l + r) >> 1;
return __gcd(queryj(i->left, l, mid, tl, tr), queryj(i->right, mid + 1, r, tl, tr));
}
struct purice {
purice *left, *right;
node* 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) {
modifj(i->paiu, 0, m - 1, 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) if(i->left->paiu) leftval = queryj(i->left->paiu, 0, m - 1, posj, posj);
if(i->right) if(i->right->paiu) rightval = queryj(i->right->paiu, 0, m - 1, posj, posj);
ll new_val = __gcd(leftval, rightval);
modifj(i->paiu, 0, m - 1, 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 queryj(i->paiu, 0, m - 1, 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);
}
