#include "game.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
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;
}
map<pii, ll> mp;
int n, m;
void init(int R, int C) {
n = R, m = C;
}
void update(int p, int q, long long k) {
mp[{p, q}] = k;
}
long long calculate(int p, int q, int u, int v) {
ll x = 0;
for (int i = p; i <= u;) {
auto it = mp.lower_bound({i, q});
while (it != mp.end() && it->x.x == i && it->x.y <= v) {
x = gcd2(x, it->y);
it++;
}
it = mp.lower_bound({i + 1, q});
i = it->x.x;
}
return x;
}
