#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;
}
#define N 1073741824
map<int, map<int, long long> > tree;
void init(int R, int C){};
long long get(map<int, long long>& pnt, int key){
auto it = pnt.find(key);
if(it == pnt.end()) return 0;
return it -> second;
}
void update(int P, int Q, long long K) {
int idx = P + N;
int idy = Q + N;
int t = idy >> 1;
auto& pntr = tree[idx];
pntr[idy] = K;
while(t){
pntr[t] = gcd2(get(pntr, t << 1), get(pntr, t << 1 | 1));
t >>= 1;
}
idx >>= 1;
while(idx){
t = idy >> 1;
auto& pntrr = tree[idx];
pntrr[idy] = gcd2(get(tree[idx << 1], idy), get(tree[idx << 1 | 1], idy));
while(t){
pntrr[t] = gcd2(get(pntrr, t << 1), get(pntrr, t << 1 | 1));
t >>= 1;
}
idx >>= 1;
}
}
long long solve(map<int, long long>& pntr, int id, int l, int r, int L, int R){
if(l > R || r < L) return 0;
if(l >= L && r <= R){
return get(pntr, id);
}
int m =(l + r) >> 1;
return gcd2(solve(pntr, id << 1, l, m, L, R), solve(pntr, id << 1 | 1, m + 1, r, L, R));
}
long long solve(int id, int l, int r, int L, int R, int U, int V){
if(l > R || r < L) return 0;
if(l >= L && r <= R){
return solve(tree[id], 1, 1, N, U, V);
}
int m = (l + r) >> 1;
return gcd2(solve(id << 1, l, m, L, R, U, V), solve(id << 1 | 1, m + 1, r, L, R, U, V));
}
long long calculate(int P, int Q, int U, int V){
return solve(1, 1, N, 1 + P, 1 + U, 1 + Q, 1 + V);
}
