#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 15001 ;
int r1 , r2 , c1 , c2 ,r , c , rowscnt = 0 , colscnt = 0, tmp1 , tmp2;
int nxt2[N * 30][2];
int nxt1[N * 30];
long long val , seg[N * 30 * 30];
int nxt3[N * 30 * 30][2];
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;
}
inline int addrow(){
nxt1[rowscnt] = -1;
nxt2[rowscnt][0] = nxt2[rowscnt][1] = -1;
return rowscnt++;
}
inline int addcol(){
seg[colscnt] = 0;
nxt3[colscnt][0] = nxt3[colscnt][1] = -1;
return colscnt++;
}
void update_cols(int s,int e,int idx){
if(s == e){
seg[idx] = val;
return;
}
if(c1 > ((s + e) >> 1)){
if(nxt3[idx][1] == -1)
nxt3[idx][1] = addcol();
update_cols(((s+e) >> 1) + 1, e, nxt3[idx][1]);
}
else{
if(nxt3[idx][0] == -1)
nxt3[idx][0] = addcol();
update_cols(s,((s+e) >> 1),nxt3[idx][0]);
}
seg[idx] = 0;
if(nxt3[idx][0] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][0]]);
if(nxt3[idx][1] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][1]]);
}
void update_cols_2(int s,int e,int idx,int l,int r){
if(s == e){
seg[idx] = 0;
if(l != -1) seg[idx] = gcd2(seg[idx],seg[l]);
if(r != -1) seg[idx] = gcd2(seg[idx],seg[r]);
return ;
}
if(c1 > ((s + e) >> 1)){
if(nxt3[idx][1] == -1)
nxt3[idx][1] = addcol();
update_cols_2(((s+e) >> 1) + 1 , e,nxt3[idx][1],(l == -1 ? -1 : nxt3[l][1]) , (r == -1 ? -1 : nxt3[r][1]));
}
else{
if(nxt3[idx][0] == -1)
nxt3[idx][0] = addcol();
update_cols_2(s , ((s+e) >> 1) , nxt3[idx][0],(l == -1 ? -1 : nxt3[l][0]) , (r == -1 ? -1 : nxt3[r][0]));
}
seg[idx] = 0;
if(nxt3[idx][0] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][0]]);
if(nxt3[idx][1] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][1]]);
}
void update_rows(int s,int e,int idx){
if(s == e){
if(nxt1[idx] == -1)
nxt1[idx] = addcol();
update_cols(0 , c , nxt1[idx]);
return;
}
if(r1 > ((s + e) >> 1)){
if(nxt2[idx][1] == -1)
nxt2[idx][1] = addrow();
update_rows(((s+e) >> 1) + 1, e,nxt2[idx][1]);
}
else{
if(nxt2[idx][0] == -1)
nxt2[idx][0] = addrow();
update_rows(s , ((s+e) >> 1), nxt2[idx][0]);
}
if(nxt1[idx] == -1)
nxt1[idx] = addcol();
tmp1 = nxt2[idx][0];
tmp2 = nxt2[idx][1];
if(tmp1 != -1)
tmp1 = nxt1[tmp1];
if(tmp2 != -1)
tmp2 = nxt1[tmp2];
update_cols_2(0 , c , nxt1[idx] , tmp1 , tmp2);
}
long long get_cols(int s,int e,int idx){
if(s > c2 || e < c1 || idx == -1)
return 0;
if(s >= c1 && e <= c2)
return seg[idx];
return gcd2(get_cols(s,((s+e) >> 1),nxt3[idx][0]),get_cols(((s+e) >> 1) + 1, e,nxt3[idx][1]));
}
long long get_rows(int s,int e,int idx){
if(s > r2 || e < r1 || idx == -1)
return 0;
if(s >= r1 && e <= r2){
return get_cols(0 , c , nxt1[idx]);
}
return gcd2(get_rows(s,((s+e) >> 1),nxt2[idx][0]),get_rows(((s+e) >> 1) + 1, e,nxt2[idx][1]));
}
void init(int R, int C) {
r = R ;
c = C;
addrow();
}
void update(int P, int Q, long long K) {
r1 = P;
c1 = Q;
val = K;
update_rows(0 , r , 0);
}
long long calculate(int P, int Q, int U, int V) {
r1 = P;
r2 = U;
c1 = Q;
c2 = V;
return get_rows(0 , r , 0);
}
