#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int linii , coloane;
struct SegmentTree {
struct Nod {
long long cmmdc = 0;
Nod *stanga = NULL , *dreapta = NULL;
} *radacina = NULL;
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));
}
void Update (const int indice , const long long valoare)
{ __Update(radacina , 0 , coloane - 1 , indice , valoare); }
long long Query (const int stanga , const int dreapta)
{ return __Query(radacina , 0 , coloane - 1 , stanga , dreapta); }
};
struct Nod {
SegmentTree urmatorul;
Nod *stanga = NULL , *dreapta = NULL;
} *rezultat = NULL;
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; }
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));
}
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);
}
