#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;
}
map < pair<int,int> , long long > mp;
int r1 , r2 , c1 , c2 , F ,r , c ;
long long val;
long long update_cols(int s,int e,int idx){
if(s > c1 || e < c1){
if(mp.find(make_pair(F,idx)) == mp.end())
return 0;
return mp[make_pair(F,idx)];
}
if(s == e){
return mp[make_pair(F,idx)] = val;
}
return mp[make_pair(F,idx)] = gcd2(update_cols(s,((s+e) >> 1),(idx << 1)),update_cols(((s+e) >> 1) + 1, e, (idx << 1) + 1));
}
void update_rows(int s,int e,int idx){
if(s > r1 || e < r1)
return;
if(s == e){
F = idx;
update_cols(0 , c , 1);
return;
}
update_rows(s,((s+e) >> 1),(idx << 1));
update_rows(((s+e) >> 1) + 1, e, (idx << 1) + 1);
F = idx;
update_cols(0 , c , 1);
}
long long get_cols(int s,int e,int idx){
if(s > c2 || e < c1 || mp.find(make_pair(F,idx)) == mp.end())
return 0;
if(s >= c1 && e <= c2)
return mp[make_pair(F,idx)];
return gcd2(get_cols(s,((s+e) >> 1),(idx << 1)),get_cols(((s+e) >> 1) + 1, e, (idx << 1) + 1));
}
long long get_rows(int s,int e,int idx){
if(s > r2 || e < r1)
return 0;
if(s >= r1 && e <= r2){
F = idx;
return get_cols(0 , c , 1);
}
return gcd2(get_rows(s,((s+e) >> 1),(idx << 1)),get_rows(((s+e) >> 1) + 1, e, (idx << 1) + 1));
}
void init(int R, int C) {
r = R ;
c = C;
}
void update(int P, int Q, long long K) {
r1 = P;
c1 = Q;
val = K;
update_rows(0 , r , 1);
}
long long calculate(int P, int Q, int U, int V) {
r1 = P;
r2 = U;
c1 = Q;
c2 = V;
return get_rows(0 , r , 1);
}
