#include "game.h"
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
ll gcd2(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
vector <vector <ll>> sgt;
int Cs;
void init(int R, int C) {
Cs = 1 << (int(ceil(log2(C))));
Cs--;
sgt.assign(R, vector<ll>(2 * Cs + 1, 0));
}
void update(int P, int Q, ll K) {
int node = Q + Cs;
sgt[P][node] = K;
while (node) {
node = (node - 1) / 2;
sgt[P][node] = gcd2(sgt[P][2 * node + 1], sgt[P][2 * node + 2]);
}
}
ll sgtget(int row, int l, int r, int node, int cl, int cr) {
if (r < cl || cr < l) return 0;
if (l <= cl && cr <= r) return sgt[row][node];
int cm = (cl + cr) / 2;
return gcd2(sgtget(row, l, r, 2 * node + 1, cl, cm), sgtget(row, l, r, 2 * node + 2, cm + 1, cr));
}
ll calculate(int P, int Q, int U, int V) {
ll r = 0;
for (int i = P; i <= U; i++) {
r = gcd2(r, sgtget(i, Q, V, 0, 0, Cs));
}
return r;
}
