#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int linii , coloane;
struct Nod {
long long cmmdc = 0;
int inceput = 0 , sfarsit = coloane - 1;
Nod *stanga = NULL , *dreapta = NULL;
};
void Update (Nod* &nod , const int indice , const long long valoare)
{
const int stanga = nod -> inceput;
const int dreapta = nod -> sfarsit;
const int mijloc = (stanga + dreapta) >> 1;
if (stanga == dreapta)
{ nod -> cmmdc = valoare; return; }
if (indice <= mijloc)
{
if (nod -> stanga == NULL)
{
nod -> stanga = new Nod;
nod -> stanga -> inceput = nod -> stanga -> sfarsit = indice;
}
else
if (indice < nod -> stanga -> inceput || nod -> stanga -> sfarsit < indice)
{
Nod *urmatorul = new Nod;
urmatorul -> inceput = stanga;
urmatorul -> sfarsit = mijloc;
const int __mijloc = (urmatorul -> inceput + urmatorul -> sfarsit) >> 1;
if (nod -> stanga -> sfarsit <= __mijloc) { urmatorul -> stanga = nod -> stanga; }
else { urmatorul -> dreapta = nod -> stanga; }
nod -> stanga = urmatorul;
}
Update(nod -> stanga , indice , valoare);
}
else
{
if (nod -> dreapta == NULL)
{
nod -> dreapta = new Nod;
nod -> dreapta -> inceput = nod -> dreapta -> sfarsit = indice;
}
else
if (indice < nod -> dreapta -> inceput || nod -> dreapta -> sfarsit < indice)
{
Nod *urmatorul = new Nod;
urmatorul -> inceput = mijloc + 1;
urmatorul -> sfarsit = dreapta;
const int __mijloc = (urmatorul -> inceput + urmatorul -> sfarsit) >> 1;
if (nod -> dreapta -> sfarsit <= __mijloc) { urmatorul -> stanga = nod -> dreapta; }
else { urmatorul -> dreapta = nod -> dreapta; }
nod -> dreapta = urmatorul;
}
Update(nod -> dreapta , indice , valoare);
}
nod -> cmmdc = __gcd(nod -> stanga ? nod -> stanga -> cmmdc : 0 , nod -> dreapta ? nod -> dreapta -> cmmdc : 0);
}
long long Query (Nod* &nod , const int stanga_query , const int dreapta_query)
{
if (nod == NULL) { return 0; }
const int stanga = nod -> inceput;
const int dreapta = nod -> sfarsit;
if (dreapta_query < stanga || dreapta < stanga_query) { return 0; }
if (stanga_query <= stanga && dreapta <= dreapta_query) { return nod -> cmmdc; }
return __gcd(Query(nod -> stanga , stanga_query , dreapta_query) , Query(nod -> dreapta , stanga_query , dreapta_query));
}
struct SegmentTree {
Nod *urmatorul = new Nod;
SegmentTree *stanga = NULL , *dreapta = NULL;
} *rezultat = NULL;
void __Update (SegmentTree* &nod , const int stanga , const int dreapta , const int linie , const int coloana , const long long valoare)
{
if (nod == NULL)
{ nod = new SegmentTree; }
if (stanga == dreapta)
{ Update(nod -> urmatorul , coloana , valoare); return; }
const int mijloc = (stanga + dreapta) >> 1;
if (linie <= mijloc) { __Update(nod -> stanga , stanga , mijloc , linie , coloana , valoare); }
else { __Update(nod -> dreapta , mijloc + 1 , dreapta , linie , coloana , valoare); }
Update(nod -> urmatorul , coloana , __gcd(nod -> stanga ? Query(nod -> stanga -> urmatorul , coloana , coloana) : 0 , nod -> dreapta ? Query(nod -> dreapta -> urmatorul , coloana , coloana) : 0) );
}
long long __Query (SegmentTree* &nod , const int stanga , const int dreapta , const int stanga_query , const int dreapta_query , const int __stanga_query , const int __dreapta_query)
{
if (dreapta_query < stanga || dreapta < stanga_query || nod == NULL)
{ return 0; }
if (stanga_query <= stanga && dreapta <= dreapta_query)
{ return Query(nod -> urmatorul , __stanga_query , __dreapta_query); }
const int mijloc = (stanga + dreapta) >> 1;
return __gcd(
__Query(nod -> stanga , stanga , mijloc , stanga_query , dreapta_query , __stanga_query , __dreapta_query) ,
__Query(nod -> dreapta , mijloc + 1 , dreapta , stanga_query , dreapta_query , __stanga_query , __dreapta_query)
);
}
void init (int __linii , int __coloane)
{
linii = __linii;
coloane = __coloane;
}
void update (int linie , int coloana , long long valoare)
{
__Update(rezultat , 0 , linii - 1 , linie , coloana , valoare);
}
long long calculate (int linie_1 , int coloana_1 , int linie_2 , int coloana_2)
{
return __Query(rezultat , 0 , linii - 1 , linie_1 , linie_2 , coloana_1 , coloana_2);
}
