#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int R, C;
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=0;
void update() {
gcd=gcd2(left->gcd, right->gcd);
}
};
vector<node*> st;
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;
int s1=query(root->left, left, mid, qLeft, qRight);
int s2=query(root->right, mid+1, right, qLeft, qRight);
return gcd2(s1, s2);
}
void updatest(node* root, int left, int right, int qLeft, int qRight, int nValue)
{
if (left>qRight || right<qLeft) return;
if (left>=qLeft && right<=qRight)
{
root->gcd=nValue;
return;
}
int mid=(left+right)/2;
updatest(root->left, left, mid, qLeft, qRight, nValue);
updatest(root->right, mid+1, right, qLeft, qRight, nValue);
root->update();
}
void build(node* root, int left, int right)
{
if (left == right) {
return;
}
root->left=new node{NULL, NULL, 0};
root->right=new node{NULL, NULL, 0};
int mid=(left+right)/2;
build(root->left, left, mid);
build(root->right, mid+1, right);
root->update();
}
#undef int
void init(int A, int B) {
#define int long long
R=A, C=B;
st.resize(R);
for (int i = 0; i < R; ++i) {
st[i]=new node{NULL, NULL, 0};
build(st[i], 1, C);
}
#undef int
}
void update(int P, int Q, long long K) {
#define int long long
updatest(st[P], 1, C, Q+1, Q+1, K);
#undef int
}
long long calculate(int P, int Q, int U, int V) {
#define int long long
int ans=0;
Q++, V++;
for (int i = P; i <= U; ++i)
{
ans=gcd2(ans, query(st[i], 1, C, Q, V));
}
return ans;
#undef int
}
