#include "game.h"
#include <bits/stdc++.h>
using namespace std;
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;
}
typedef pair<int,int> ii;
struct pair_hash
{
template <class T1, class T2>
std::size_t operator() (const std::pair<T1, T2> &pair) const
{
return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
}
};
static unordered_map<ii, long long, pair_hash> tree;
int N, M;
void init(int R, int C) {
N = R; M = C;
return;
}
void update(int r, int c, long long v) {
int nr = N + r;
int nc = M + c;
tree[ii(nr,nc)] = v;
while(nr > 0){
nc = M + c;
while(nc > 0){
if(nr < N){
tree[ii(nr,nc)] = gcd2(tree[ii(nr<<1,nc)],tree[ii(nr<<1|1,nc)]);
}
else if(nc < M){
tree[ii(nr,nc)] = gcd2(tree[ii(nr,nc<<1)],tree[ii(nr,nc<<1|1)]);
}
else tree[ii(nr,nc)] = v;
nc >>= 1;
}
nr >>= 1;
}
}
long long calculate(int t, int l, int b, int r) {
long long ans = 0;
b++; r++;
for(t += N, b += N;t < b;t >>= 1, b >>= 1){
if(t&1){
for(int nl = l+M, nr = r+M;nl < nr;nr >>= 1, nl >>= 1){
if(nl&1){
ans = gcd2(ans, tree[ii(t,nl)]);
//cout << t << " " << nl << "\n";
nl++;
}
if(nr&1){
nr--;
ans = gcd2(ans, tree[ii(t,nr)]);
//cout << t << " " << nr << "\n";
}
}
t++;
}
if(b&1){
b--;
for(int nl = l+M, nr = r+M;nl < nr;nr >>= 1, nl >>= 1){
if(nl&1){
ans = gcd2(ans, tree[ii(b,nl)]);
//cout << b << " " << nl << "\n";
nl++;
}
if(nr&1){
nr--;
ans = gcd2(ans, tree[ii(b,nr)]);
//cout << b << " " << nr << "\n";
}
}
}
}
//cout << endl;
return ans;
}
