#include "game.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef long long ll;
int R;
int C;
ll gcd(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct TreeRow
{
vector<ll> tree;;
TreeRow()
{
tree.resize(4 * C);
}
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;
}
};
vector<TreeRow> tree;
void ins(int x, int y, ll num, int a, int b, int node)
{
if (a == b)
{
tree[node].ins(y, num, 0, C - 1, 1);
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);
tree[node].ins(y, gcd(tree[node * 2].getAt(y, y, 0, C - 1, 1), tree[node * 2 + 1].getAt(y, y, 0, C - 1, 1)), 0, C - 1, 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, C - 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) {
R = r;
C = c;
tree.resize(4 * R);
}
void update(int P, int Q, ll K) {
ins(P, Q, K, 0, R - 1, 1);
}
ll calculate(int P, int Q, int U, int V) {
/* ... */
return getAt(P, U, Q, V, 0, R - 1, 1);
}
