#include "game.h"
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <vector>
#include <fstream>
#include <bitset>
#include <tuple>
#include <cmath>
#include <cstdint>
#include <stack>
#include <cassert>
#include <cstdio>
#include <queue>
#include <iterator>
#include <iomanip>
#include <algorithm>
#include <sstream>
const int MAX_C = 100000;
const int MAX_R = 100;
int r, c;
using namespace std;
#define int long long
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;
}
struct node {
node* left, * right;
int gcd;
void updates() {
gcd = gcd2(left->gcd, right->gcd);
}
};
vector<node*> roots;
int query(node* root, int left, int right, int qLeft, int qRight) {
if (left > qRight || right < qLeft) return 0;
if (left >= qLeft && right <= qRight) return root->gcd;
int mid = (left + right) / 2;
return gcd2(query(root->left, left, mid, qLeft, qRight), query(root->right, mid + 1, right, qLeft, qRight));
}
void update_(node* root, int left, int right, int point, int nValue) {
int qLeft, qRight;
qLeft = qRight = point;
if (left > qRight || right < qLeft) return;
if (left >= qLeft && right <= qRight) {
root->gcd = nValue;
return;
}
int mid = (left + right) / 2;
update_(root->left, left, mid, point, nValue);
update_(root->right, mid + 1, right, point, nValue);
root->updates();
}
void build(node* root, int left, int right) {
if (left == right) {
root->gcd = 0;
return;
}
int mid = (left + right) / 2;
root->left = new node{ NULL, NULL, 0 };
root->right = new node{ NULL, NULL, 0 };
build(root->left, left, mid);
build(root->right, mid + 1, right);
root->updates();
}
void destroy(node* root) {
if (root->left) destroy(root->left);
if (root->right) destroy(root->right);
delete root;
}
void init(signed R, signed C) {
r = R;
c = C;
roots.resize(r);
for (int i = 0; i < r; i++)
{
roots[i] = new node{ NULL, NULL, 0 };
build(roots[i], 0, c - 1);
}
vector<node*> rootasd=roots;
return;
}
void update(signed P, signed Q, long long K) {
update_(roots[P], 0, c - 1, Q, K);
}
long long calculate(signed P, signed Q, signed U, signed V) {
int gcd = 0;
for (int i = P; i <= U; i++)
{
gcd = gcd2(query(roots[i], 0, c - 1, Q, V), gcd);
}
return gcd;
}
