#include "game.h"
#include <vector>
#include <iostream>
#include <array>
#include <cassert>
#define int long long
#define par array<int,2>
using namespace std;
int gcd(int a, int b)
{
if (a > b) swap(a, b);
if (a == 0) return b;
return gcd(b % a, a);
}
struct segtree
{
vector<int> table;
int query(int ql, int qr, int l, int r, int pos)
{
if (ql <= l && r <= qr) return table[pos];
if (r < ql || qr < l) return 0;
return gcd(query(ql, qr, l, (l + r)/2, 2*pos + 1), query(ql, qr, (l + r)/2 + 1, r, 2*pos + 2));
}
void update(int k, int v, int l, int r, int pos)
{
if (l == r)
{
table[pos] = v;
return;
}
if (k <= (l + r)/2) update(k, v, l, (l + r)/2, 2*pos + 1);
else update(k, v, (l + r)/2 + 1, r, 2*pos + 2);
table[pos] = gcd(table[2*pos + 1], table[2*pos + 2]);
}
};
vector<segtree> sts;
int r, c;
void init(signed R, signed C)
{
r = R;
c = C;
sts.resize(R);
for (int i = 0; i < R; i++) sts[i].table.resize(4*C);
}
void update(signed P, signed Q, int K)
{
// cout << "\n";
sts[P].update(Q, K, 0, c - 1, 0);
}
int calculate(signed P, signed Q, signed U, signed V)
{
// cout << "\n";
if (U < P) swap(U, P);
if (V < Q) swap(Q, V);
int ret = 0;
for (int i = P; i <= U; i++)
{
ret = gcd(ret, sts[i].query(Q, V, 0, c - 1, 0));
// cout << i << " " << sts[i].query(Q, V, 0, c - 1, 0) << "\n";
}
return ret;
}
