#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
vector<ll> v[10][30];
int level,zereg[30];
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;
}
ll val;
int l,r;
void dfs(int num, int k, int x) {
int y = zereg[level - k] * x;
int z = zereg[level - k] * (x + 1) - 1;
if(l <= y && z <= r) {
val = gcd2(val, v[num][k][x]);
return;
}
if(z < l || y > r || k == level) return;
dfs(num, k + 1, x * 2);
dfs(num, k + 1, x * 2 + 1);
}
int rr,cc;
ll z[200][200];
bool ok = 0;
void init(int R, int C) {
/* ... */
if(R <= 100 && C <= 100) {
ok = 1;
return;
}
zereg[0] = 1;
for(int i = 0; i <= 30; i ++) {
if(zereg[i] >= C) {
level = i;
break;
}
zereg[i + 1] = zereg[i] * 2;
}
for(int x = 0; x < R; x ++) {
for(int i = 0; i <= level; i ++) {
for(int j = 0; j < zereg[i]; j ++) {
v[x][i].pb(0);
}
}
}
}
void update(int P, int Q, long long K) {
if(ok == 1) {
z[P][Q] = K;
return;
}
v[P][level][Q] = K;
for(int i = level - 1; i >= 0; i --) {
Q /= 2;
v[P][i][Q] = gcd2(v[P][i + 1][Q * 2], v[P][i + 1][Q * 2 + 1]);
}
// for(int i = 0; i <= level; i ++) {
// for(int j = 0; j < zereg[i]; j ++) {
// cout << v[P][i][j] << ' ' ;
// }
// cout << '\n';
// }
/* ... */
}
long long calculate(int P, int Q, int U, int V) {
long long ret = 0;
if(ok == 1) {
for(int i = P; i <= U; i ++) {
for(int j = Q; j <= V; j ++) {
ret = gcd2(ret, z[i][j]);
}
}
return ret;
}
//cout << "FK: " << P << ' ' << Q << ' ' << U << ' ' << V << '\n';
for(int i = P; i <= U; i ++) {
val = 0;
l = Q;
r = V;
dfs(i,0,0);
ret = gcd2(val,ret);
// cout << ret << " // \n";
}
return ret;
/* ... */
}
