#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;
}
const int MAXN = 1e5 + 10;
long long st[10][4 * MAXN];
void u(int l, int r, int row, int tar, int idx, long long val) {
if(l == r) {
st[row][idx] = val;
return;
}
int mid = (l + r) >> 1;
if(tar <= mid) u(l, mid, row, tar, (idx<<1) + 1, val);
else u(mid+1, r, row, tar, (idx<<1) + 2, val);
st[row][idx] = gcd2(st[row][(idx<<1) + 1], st[row][(idx<<1) + 2]);
}
long long qu(int l, int r, int constl, int constr, int row, int idx) {
if(l <= constl && constr <= r) return st[row][idx];
int mid = (constl + constr) >> 1;
if(mid < l || r < constl) return qu(l, r, mid+1, constr, row, (idx<<1) + 2);
else if(constr < l || r < mid+1) return qu(l, r, constl, mid, row, (idx<<1) + 1);
else {
return gcd2(qu(l, r, constl, mid, row, (idx<<1) + 1), qu(l, r, mid+1, constr, row, (idx<<1) + 2));
}
}
long long brute[100][100];
int r, c;
void init(int R, int C) {
r = R;
c = C;
}
void update(int P, int Q, long long K) {
if(max(r, c) < 100) {
brute[P][Q] = K; return;
}
u(0, c - 1, P, Q, 0, K);
}
long long calculate(int P, int Q, int U, int V) {
if(max(U, V) < 100) {
long long ans = 0;
for(int i=P; i<=U; i++) {
for(int j=Q; j<=V; j++) {
ans = gcd2(ans, brute[i][j]);
}
}
return ans;
}
long long ans = 0;
for(int i=P; i<=U; i++) ans = gcd2(ans, qu(Q, V, 0, c - 1, i, 0));
return ans;
}
/*
g++ -std=c++17 -O2 -o T2444 grador.cpp T2444.cpp
./T2444 < input.txt
*/
