#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
const int maxr = 1e9+5;
const int maxc = 1e9+5;
long long gcd2(long long X, long long Y)
{
if(X == 0 || Y == 0)
{
return X+Y;
}
long long tmp;
while(X != Y && Y != 0)
{
tmp = X;
X = Y;
Y = tmp%Y;
}
return X;
}
struct layer2_node
{
layer2_node(int low, int high) : low(low), high(high), left(NULL), right(NULL), value(0LL) {}
int low, high;
layer2_node *left;
layer2_node *right;
ll value;
};
struct layer1_node
{
layer1_node() : left(NULL), right(NULL), l2(0, maxc) {}
layer1_node *left, *right;
layer2_node l2;
};
static layer1_node root;
static void update2(layer2_node* node, int Q, long long K)
{
int low = node->low;
int high = node->high;
int mid = (low+high)/2;
if(low == high)
{
node->value = K;
return;
}
layer2_node*& tgt = Q<=mid ? node->left : node->right;
if(tgt == NULL)
{
tgt = new layer2_node(Q, Q);
tgt->value = K;
}
else if(tgt->low <= Q && Q<= tgt->high)
{
update2(tgt, Q, K);
}
else
{
do
{
if(Q<= mid) high = mid;
else low = mid+1;
mid = (low+high)/2;
}
while((Q<= mid) == (tgt->low <= mid));
layer2_node* newnode = new layer2_node(low, high);
(tgt->low<= mid? newnode->left : newnode->right) = tgt;
tgt = newnode;
update2(newnode, Q, K);
}
node->value = gcd2(node->left? node->left->value: 0, node->right?node->right->value:0);
}
ll query2(layer2_node *nd, int A, int B)
{
if(nd == NULL || B< nd->low || A> nd->high) return 0;
else if(A<= nd->low && nd->high <= B) return nd->value;
return gcd2(query2(nd->left, A, B), query2(nd->right, A, B));
}
static void update1(layer1_node *node, int low, int high, int P, int Q, ll K)
{
int mid = (low+high)/2;
if(low == high)
{
update2(&node->l2, Q, K);
}
else
{
layer1_node*& newnode = P<= mid? node->left : node->right;
if(P<= mid) high = mid;
else low = mid+1;
if(newnode == NULL)
{
newnode = new layer1_node();
}
update1(newnode, low, high, P, Q, K);
K = gcd2(node->left?query2(&node->left->l2, Q, Q) : 0, node->right?query2(&node->right->l2, Q, Q) : 0);
update2(&node->l2, Q, K);
}
}
ll query1(layer1_node* nd, int low, int high, int A1, int B1, int A2, int B2)
{
if(nd == NULL || B1< low || high < A1)
{
return 0;
}
else if(A1<= low && high<= B1)
{
return query2(&nd->l2, A2, B2);
}
int mid = (low+high)/2;
return gcd2(query1(nd->left, low, mid, A1, B1, A2, B2), query1(nd->right, mid+1, high, A1, B1, A2, B2));
}
void init(int R, int C){}
void update(int P, int Q, long long K)
{
update1(&root, 0, maxr, P, Q, K);
}
long long calculate(int P, int Q, int U, int V)
{
return query1(&root, 0, maxr, P, U, Q, V);
}
