#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
ll bigNum = 1073741824;
ll mult = 1000000007;
ll r, c, p, q, u, v;
//ll segTree[32][262144];
unordered_map<ll, ll> segTree;
void init(int R, int C) {
r = R;
c = C;
}
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;
}
void update(int p, int q, ll k) {
p += bigNum;
q += bigNum;
auto trash = segTree.find(mult * p + q);
if (trash != segTree.end())
{
segTree.erase(trash);
}
segTree.insert({mult * p + q, k});
while (q > 0)
{
//cout << "Outerwhile q = " << q << "\n";
ll pTemp = p/2;
while (pTemp > 0)
{
//cout <<"Innerwhile p temp = " << pTemp << "\n";
auto place1 = segTree.find(mult*2*pTemp + q);
ll value1;
if (place1 == segTree.end())
{
value1 = 0;
}
else
{
value1 = place1->second;
}
auto place2 = segTree.find(mult*(2*pTemp+1) + q);
ll value2;
if (place2 == segTree.end())
{
value2 = 0;
}
else
{
value2 = place2->second;
}
trash = segTree.find(mult*pTemp + q);
if (trash != segTree.end())
{
segTree.erase(trash);
}
segTree.insert({mult*pTemp+ q, gcd2(value1, value2)});
pTemp /= 2;
}
q /= 2;
auto place1 = segTree.find(mult*p + 2*q);
ll value1;
if (place1 == segTree.end())
{
value1 = 0;
}
else
{
value1 = place1->second;
}
auto place2 = segTree.find(mult*p + 2*q+1);
ll value2;
if (place2 == segTree.end())
{
value2 = 0;
}
else
{
value2 = place2->second;
}
trash = segTree.find(mult*p+ q);
if (trash != segTree.end())
{
segTree.erase(trash);
}
segTree.insert({mult*p+q, gcd2(value1, value2) });
//cout << "End of outerwhile q = " << q << "\n";
}
}
ll getSegTree(ll nodex, ll nodey, ll nodexstart, ll nodexend, ll nodeystart, ll nodeyend) {
if (nodexstart > u or nodexend < p or nodeystart > v or nodeyend < q)
{
return 0;
}
if (nodexstart >= p and nodexend <= u)
{
if (nodeystart >= q and nodeyend <= v)
{
auto ansPlace = segTree.find(mult*nodex + nodey);
if (ansPlace == segTree.end())
{
return 0;
}
//cout << "Returning " << nodex << "," << nodey << " which is " << ansPlace->second;
return ansPlace->second;
}
ll midy = (nodeystart + nodeyend)/2;
return gcd2(getSegTree(nodex, 2*nodey, nodexstart, nodexend, nodeystart, midy), getSegTree(nodex, 2*nodey+1, nodexstart, nodexend, midy+1, nodeyend));
}
ll midx = (nodexstart + nodexend)/2;
return gcd2(getSegTree(2*nodex, nodey, nodexstart, midx, nodeystart, nodeyend), getSegTree(2*nodex+1, nodey, midx + 1, nodexend, nodeystart, nodeyend));
}
ll calculate(int P, int Q, int U, int V) {
p = P;
q = Q;
u = U;
v = V;
return getSegTree(1, 1, 0, bigNum-1, 0, bigNum-1);
}
