#include "game.h"
#include <bits/stdc++.h>
using namespace std;
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 segtree
{
int size;
vector<int> values;
void init(int n) {
size=n;
values.resize(2 * size + 2);
}
void set(int i, int v, int x, int qLeft, int qRight) {
if (qLeft>=i && i>=qRight) {
values[x]=v;
return;
}
int mid = (qLeft + qRight) / 2;
if (i>mid) {
set(i, v, 2*x + 1, mid+1, qRight);
} else {
set(i, v, 2*x, qLeft, mid);
}
values[x]=gcd2(values[2*x], values[2*x + 1]);
}
void set(int i, int v) {
set(i, v, 1, 1, size);
}
int calc(int left, int right, int x, int qLeft, int qRight) {
if (qLeft > right || qRight < left) return 0;
if (qLeft >= left && qRight <= right) return values[x];
int mid = (qLeft + qRight) / 2;
int s1 = calc(left, right, 2*x, qLeft, mid);
int s2 = calc(left, right, 2*x + 1, mid+1, qRight);
return gcd2(s1, s2);
}
int calc(int left, int right) {
return calc(left, right, 1, 1, size);
}
};
vector<segtree> st;
void init(int R, int C) {
R++, C++;
st.resize(R);
int size=1;
while (size < C) size*=2;
for (int i = 1; i <= R; ++i) st[i].init(size);
}
void update(int P, int Q, long long K) {
st[P+1].set(Q+1, K);
}
long long calculate(int P, int Q, int U, int V) {
int ans=0;
P++, Q++, U++, V++;
for (int i = P; i <= U; ++i)
{
ans=gcd2(ans, st[i].calc(Q, V));
}
return ans;
}
