#include "game.h"
#include <bits/stdc++.h>
using namespace std;
class SegmentTree {
private:
struct Nod {
long long cmmdc = 0;
Nod *stanga = NULL , *dreapta = NULL;
} *radacina;
int lungime;
void __Update (Nod* &nod , const int stanga , const int dreapta , const int indice , const long long valoare)
{
if (nod == NULL)
{ nod = new Nod; }
if (stanga == dreapta)
{ nod -> cmmdc = valoare; return; }
const int mijloc = (stanga + dreapta) >> 1;
if (indice <= mijloc) { __Update(nod -> stanga , stanga , mijloc , indice , valoare); }
else { __Update(nod -> dreapta , mijloc + 1 , 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 , const int dreapta , 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 nod -> cmmdc; }
const int mijloc = (stanga + dreapta) >> 1;
return __gcd(__Query(nod -> stanga , stanga , mijloc , stanga_query , dreapta_query) , __Query(nod -> dreapta , mijloc + 1 , dreapta , stanga_query , dreapta_query));
}
public:
SegmentTree (const int __lungime) { lungime = __lungime; radacina = NULL; }
~SegmentTree () { }
void Update (const int indice , const long long valoare)
{ __Update(radacina , 0 , lungime - 1 , indice , valoare); }
long long Query (const int stanga , const int dreapta)
{ return __Query(radacina , 0 , lungime - 1 , stanga , dreapta); }
};
class SegmentTree2D {
private:
struct Nod {
SegmentTree urmatorul;
Nod *stanga = NULL , *dreapta = NULL;
Nod (const int coloane = 0) : urmatorul(coloane) { }
} *radacina;
int linii , coloane;
void __Update (Nod* &nod , const int stanga , const int dreapta , const int linie , const int coloana , const long long valoare)
{
if (nod == NULL)
{ nod = new Nod(coloane); }
if (stanga == dreapta)
{ nod -> urmatorul.Update(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); }
nod -> urmatorul.Update(coloana , __gcd(nod -> stanga ? nod -> stanga -> urmatorul.Query(coloana , coloana) : 0 , nod -> dreapta ? nod -> dreapta -> urmatorul.Query(coloana , coloana) : 0));
}
long long __Query (Nod* &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 nod -> urmatorul.Query(__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));
}
public:
SegmentTree2D (const int __linii , const int __coloane) { linii = __linii; coloane = __coloane; radacina = NULL; }
~SegmentTree2D () { }
void Update (const int linie , const int coloana , const long long valoare)
{ __Update(radacina , 0 , linii - 1 , linie , coloana , valoare); }
long long Query (const int stanga , const int dreapta , const int __stanga , const int __dreapta)
{ return __Query(radacina , 0 , linii - 1 , stanga , dreapta , __stanga , __dreapta); }
} *rezultat;
void init (int linii , int coloane)
{
rezultat = new SegmentTree2D(linii , coloane);
}
void update (int linie , int coloana , long long valoare)
{
rezultat -> Update(linie , coloana , valoare);
}
long long calculate (int linie_1 , int coloana_1 , int linie_2 , int coloana_2)
{
return rezultat -> Query(linie_1 , linie_2 , coloana_1 , coloana_2);
}
