#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 Rs, Cs;
void init(int R, int C) {
Rs = 1 << (int(ceil(log2(R))));
Cs = 1 << (int(ceil(log2(C))));
Rs--; Cs--;
sgt.assign(2 * Rs + 1, vector<ll>(2 * Cs + 1, 0));
}
void update(int P, int Q, ll K) {
int row = P + Rs, col = Q + Cs;
sgt[row][col] = K;
while (col) {
col = (col - 1) / 2;
sgt[row][col] = gcd2(sgt[row][2 * col + 1], sgt[row][2 * col + 2]);
}
while (row) {
row = (row - 1) / 2;
col = Q + Cs;
sgt[row][col] = gcd2(sgt[2 * row + 1][col], sgt[2 * row + 2][col]);
while (col) {
col = (col - 1) / 2;
sgt[row][col] = gcd2(sgt[row][2 * col + 1], sgt[row][2 * col + 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 sgtget2(int rl, int rr, int l, int r, int node, int cl, int cr) {
if (rr < cl || cr < rl) return 0;
if (rl <= cl && cr <= rr) return sgtget(node, l, r, 0, 0, Cs);
int cm = (cl + cr) / 2;
return gcd2(sgtget2(rl, rr, l, r, 2 * node + 1, cl, cm), sgtget2(rl, rr, l, r, 2 * node + 2, cm + 1, cr));
}
ll calculate(int P, int Q, int U, int V) {
return sgtget2(P, U, Q, V, 0, 0, Rs);
}
