#include "game.h"
#include <bits/stdc++.h>
using namespace std;
class SegmentTree {
private:
struct Nod {
long long cmmdc = 0;
int stanga = 0 , dreapta = 0;
};
vector <Nod> arbore;
int lungime , numar_noduri;
void __Update (const int nod , const int stanga , const int dreapta , const int indice , const long long valoare)
{
if (stanga == dreapta) { arbore[nod].cmmdc = valoare; return; }
const int mijloc = (stanga + dreapta) >> 1;
if (indice <= mijloc) {
if (!arbore[nod].stanga) { arbore[nod].stanga = ++numar_noduri; arbore.push_back(Nod()); }
__Update(arbore[nod].stanga , stanga , mijloc , indice , valoare);
} else {
if (!arbore[nod].dreapta) { arbore[nod].dreapta = ++numar_noduri; arbore.push_back(Nod()); }
__Update(arbore[nod].dreapta , mijloc + 1 , dreapta , indice , valoare);
}
arbore[nod].cmmdc = __gcd(arbore[arbore[nod].stanga].cmmdc , arbore[arbore[nod].dreapta].cmmdc);
}
long long __Query (const int nod , const int stanga , const int dreapta , const int stanga_query , const int dreapta_query)
{
if (dreapta_query < stanga || dreapta < stanga_query || nod == 0) { return 0; }
if (stanga_query <= stanga && dreapta <= dreapta_query) { return arbore[nod].cmmdc; }
const int mijloc = (stanga + dreapta) >> 1;
return __gcd(__Query(arbore[nod].stanga , stanga , mijloc , stanga_query , dreapta_query) , __Query(arbore[nod].dreapta , mijloc + 1 , dreapta , stanga_query , dreapta_query));
}
public:
SegmentTree (const int __lungime) { lungime = __lungime; numar_noduri = 1; arbore.resize(2); }
~SegmentTree () { }
void Update (const int indice , const long long valoare)
{ __Update(1 , 0 , lungime - 1 , indice , valoare); }
long long Query (const int stanga , const int dreapta)
{ return __Query(1 , 0 , lungime - 1 , stanga , dreapta); }
};
class SegmentTree2D {
private:
struct __Nod {
SegmentTree urmatorul;
int stanga = 0 , dreapta = 0;
__Nod (const int coloane = 0) : urmatorul(coloane) { }
};
vector <__Nod> arbore;
int linii , coloane , numar_noduri;
void __Update (const int nod , const int stanga , const int dreapta , const int linie , const int coloana , const long long valoare)
{
arbore[nod].urmatorul.Update(coloana , valoare);
if (stanga == dreapta) { return; }
const int mijloc = (stanga + dreapta) >> 1;
if (linie <= mijloc) {
if (!arbore[nod].stanga) { arbore[nod].stanga = ++numar_noduri; arbore.push_back(__Nod(coloane)); }
__Update(arbore[nod].stanga , stanga , mijloc , linie , coloana , valoare);
} else {
if (!arbore[nod].dreapta) { arbore[nod].dreapta = ++numar_noduri; arbore.push_back(__Nod(coloane)); }
__Update(arbore[nod].dreapta , mijloc + 1 , dreapta , linie , coloana , valoare);
}
}
long long __Query (const int 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 == 0) { return 0; }
if (stanga_query <= stanga && dreapta <= dreapta_query) { return arbore[nod].urmatorul.Query(__stanga_query , __dreapta_query); }
const int mijloc = (stanga + dreapta) >> 1;
return __gcd(__Query(arbore[nod].stanga , stanga , mijloc , stanga_query , dreapta_query , __stanga_query , __dreapta_query) , __Query(arbore[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; numar_noduri = 1; arbore.resize(2 , __Nod(coloane)); }
~SegmentTree2D () { }
void Update (const int linie , const int coloana , const long long valoare)
{ __Update(1 , 0 , linii - 1 , linie , coloana , valoare); }
long long Query (const int stanga , const int dreapta , const int __stanga , const int __dreapta)
{ return __Query(1 , 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);
}
