#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 st2d
{
vector<vector<int>> table;
vector<int> ns;
int query(par ql, par qr, int l, int r, par pos, int dim)
{
// cout << dim << " " << ql[dim] << " " << qr[dim] << " " << l << " " << r << " " << pos[0] << " " << pos[1] << "\n";
if (ql[dim] <= l && r <= qr[dim])
{
if (dim == 1) return table[pos[0]][pos[1]];
return query(ql, qr, 0, ns[1] - 1, pos, dim + 1);
}
if (r < ql[dim] || qr[dim] < l) return 0;
par p1 = pos;
par p2 = pos;
p1[dim] = 2*pos[dim] + 1;
p2[dim] = 2*pos[dim] + 2;
return gcd(query(ql, qr, l, (l + r)/2, p1, dim), query(ql, qr, (l + r)/2 + 1, r, p2, dim));
}
void update(par k, int v, int l, int r, par pos, int dim)
{
if (l == r)
{
if (dim == 1) table[pos[0]][pos[1]] = v;
else update(k, v, 0, ns[1] - 1, pos, dim + 1);
return;
}
par p1 = pos;
par p2 = pos;
p1[dim] = 2*pos[dim] + 1;
p2[dim] = 2*pos[dim] + 2;
if (k[dim] <= (l + r)/2) update(k, v, l, (l + r)/2, p1, dim);
else update(k, v, (l + r)/2 + 1, r, p2, dim);
if (dim == 1) table[pos[0]][pos[1]] = gcd(table[pos[0]][2*pos[1] + 1], table[pos[0]][2*pos[1] + 2]);
else
{
for (int i = 0; i < 4*ns[1]; i++)
{
table[pos[0]][i] = gcd(table[2*pos[0] + 1][i], table[2*pos[0] + 2][i]);
}
}
}
void print()
{
for (auto t : table)
{
for (auto i : t) cout << i << " ";
cout << "\n";
}
cout << "\n";
}
};
st2d st;
int r;
int c;
void init(signed R, signed C)
{
r = R;
c = C;
st.table.resize(4*R, vector<int>(4*C));
st.ns.resize(2);
st.ns[0] = R;
st.ns[1] = C;
}
void update(signed P, signed Q, int K)
{
// cout << "\n";
st.update({P, Q}, K, 0, r - 1, {0, 0}, 0);
// st.print();
}
int calculate(signed P, signed Q, signed U, signed V)
{
// cout << "\n";
if (U < P) swap(U, P);
if (V < Q) swap(Q, V);
assert(P <= U);
assert(Q <= V);
int ret = st.query({P, Q}, {U, V}, 0, r - 1, {0, 0}, 0);
// cout << "Ok: " << ret << "\n";
return ret;
}
