#include "game.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
typedef long long llong;
const int MAXQ = 250000 + 10;
const int MAXU = 22000 + 10;
llong gcd(const llong &x, const llong &y)
{
if (x == 0) return y;
if (y == 0) return x;
return std::__gcd(x, y);
}
int R, C;
struct DynamicSegmentTree2D
{
struct DynamicSegmentTree
{
struct Node
{
llong value;
int l, r;
Node()
{
l = r = value = 0;
}
};
int cnt;
std::vector <Node> tree;
void update(int l, int r, int node, int queryPos, llong value)
{
if (l == r)
{
tree[node].value = gcd(tree[node].value, value);
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid)
{
if (tree[node].l == 0)
{
Node newNode;
tree.push_back(newNode);
tree[node].l = cnt++;
}
update(l, mid, tree[node].l, queryPos, value);
} else
{
if (tree[node].r == 0)
{
Node newNode;
tree.push_back(newNode);
tree[node].r = cnt++;
}
update(mid + 1, r, tree[node].r, queryPos, value);
}
tree[node].value = gcd(tree[tree[node].l].value, tree[tree[node].r].value);
}
llong query(int l, int r, int node, int queryL, int queryR)
{
if (node == 0 || r < queryL || queryR < l)
{
return 0;
}
if (queryL <= l && r <= queryR)
{
return tree[node].value;
}
int mid = (l + r) / 2;
return gcd(query(l, mid, tree[node].l, queryL, queryR), query(mid + 1, r, tree[node].r, queryL, queryR));
}
void update(int pos, llong value)
{
update(1, C, 1, pos, value);
}
llong query(int l, int r)
{
return query(1, C, 1, l, r);
}
int l, r;
DynamicSegmentTree()
{
cnt = 2;
Node newNode;
tree.push_back(newNode);
tree.push_back(newNode);
l = r = 0;
}
};
int cnt;
std::vector <DynamicSegmentTree> tree;
DynamicSegmentTree2D()
{
cnt = 2;
DynamicSegmentTree newNode;
tree.push_back(newNode);
tree.push_back(newNode);
}
void update(int l, int r, int node, int queryROW, int queryCOL, llong value)
{
tree[node].update(queryCOL, value);
if (l == r)
{
return;
}
int mid = (l + r) / 2;
if (queryROW <= mid)
{
if (tree[node].l == 0)
{
DynamicSegmentTree newNode;
tree.push_back(newNode);
tree[node].l = cnt++;
}
update(l, mid, tree[node].l, queryROW, queryCOL, value);
} else
{
if (tree[node].r == 0)
{
DynamicSegmentTree newNode;
tree.push_back(newNode);
tree[node].r = cnt++;
}
update(mid + 1, r, tree[node].r, queryROW, queryCOL, value);
}
}
llong query(int l, int r, int node, int queryLROW, int queryRROW, int queryLCOL, int queryRCOL)
{
if (node == 0 || r < queryLROW || queryRROW < l)
{
return 0;
}
if (queryLROW <= l && r <= queryRROW)
{
return tree[node].query(queryLCOL, queryRCOL);
}
int mid = (l + r) / 2;
return gcd(query(l, mid, tree[node].l, queryLROW, queryRROW, queryLCOL, queryRCOL),
query(mid + 1, r, tree[node].r, queryLROW, queryRROW, queryLCOL, queryRCOL));
}
void update(int row, int col, llong value)
{
update(1, R, 1, row, col, value);
}
llong query(int rowL, int colL, int rowR, int colR)
{
return query(1, R, 1, rowL, rowR, colL, colR);
}
};
DynamicSegmentTree2D tree;
void init(int _R, int _C)
{
R = _R;
C = _C;
/* ... */
}
void update(int P, int Q, long long K)
{
P++; Q++;
tree.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V)
{
P++; Q++; U++; V++;
return tree.query(P, Q, U, V);
}
