#include "game.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef long long ll;
const int N = 2005;
ll gcd(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct TreeRow
{
ll tree[4 * N];
TreeRow()
{
for (int i = 0; i < N; i++) tree[i] = 0;
}
void ins(int i, ll num, int a, int b, int node)
{
if (a == b)
{
tree[node] = num;
return;
}
int mid = (a + b) / 2;
if (i <= mid) ins(i, num, a, mid, node * 2);
else ins(i, num, mid + 1, b, node * 2 + 1);
tree[node] = gcd(tree[node * 2], tree[node * 2 + 1]);
}
ll getAt(int from, int to, int a, int b, int node)
{
if (from <= a && b <= to)
{
return tree[node];
}
int mid = (a + b) / 2;
ll res = 0;
if (from <= mid) res = gcd(res, getAt(from, to, a, mid, node * 2));
if (to > mid) res = gcd(res, getAt(from, to, mid + 1, b, node * 2 + 1));
return res;
}
};
TreeRow tree[4 * N];
void ins(int x, int y, ll num, int a, int b, int node)
{
tree[node].ins(y, num, 0, N - 1, 1);
if (a == b)
{
return;
}
int mid = (a + b) / 2;
if (x <= mid) ins(x, y, num, a, mid, node * 2);
else ins(x, y, num, mid + 1, b, node * 2 + 1);
}
ll getAt(int x1, int x2, int y1, int y2, int a, int b, int node)
{
if (x1 <= a && b <= x2)
{
return tree[node].getAt(y1, y2, 0, N - 1, 1);
}
int mid = (a + b) / 2;
ll res = 0;
if (x1 <= mid) res = gcd(res, getAt(x1, x2, y1, y2, a, mid, node * 2));
if (x2 > mid) res = gcd(res, getAt(x1, x2, y1, y2, mid + 1, b, node * 2 + 1));
return res;
}
void init(int r, int c) {
}
void update(int P, int Q, ll K) {
ins(P, Q, K, 0, N - 1, 1);
}
ll calculate(int P, int Q, int U, int V) {
/* ... */
return getAt(P, U, Q, V, 0, N - 1, 1);
}
