#include "game.h"
// #if DEBUG
#pragma GCC optimize("Ofast,fast-math,unroll-loops,O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #endif
#include <assert.h>
#include <string.h>
#include <time.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <fstream>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using namespace std::chrono;
#define SZ(x) ((int)x.size())
#define all(a) a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()
#define clrall(name, val) memset(name, (val), sizeof(name))
#define eraseDuplicate(v) v.resize(distance(v.begin(), unique(all(v))))
#define EPS 1e-9
#define ll long long
#define ull long long unsigned
#define SF scanf
#define PF printf
#define sf scanf
#define pf printf
#define psb(b) push_back((b))
#define ppb() pop_back()
#define oo (1 << 28)
#define inf 0x3f3f3f3f
#define mp make_pair
#define mt make_tuple
#define get(a, b) get<b>(a)
#define fs first
#define sc second
#define Read freopen("in.txt", "r", stdin)
#define Write freopen("out.txt", "w", stdout)
#define __ std::ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl "\n"
#define casePrint(cas) cout << "Case " << cas << ": "
#define casePrintNL(cas) cout << "Case " << cas << ":\n"
template <class T>
inline T _lcm(T a, T b)
{
T g = _gcd(a, b);
return ((a / g) * b);
}
template <class T1>
void deb(T1 e1)
{
cerr << e1 << "\n";
}
template <class T1, class T2>
void deb(T1 e1, T2 e2)
{
cerr << e1 << " " << e2 << "\n";
}
template <class T1, class T2, class T3>
void deb(T1 e1, T2 e2, T3 e3)
{
cerr << e1 << " " << e2 << " " << e3 << "\n";
}
template <class T1, class T2, class T3, class T4>
void deb(T1 e1, T2 e2, T3 e3, T4 e4)
{
cerr << e1 << " " << e2 << " " << e3 << " " << e4 << "\n";
}
template <class T1, class T2, class T3, class T4, class T5>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5)
{
cerr << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << "\n";
}
template <class T1, class T2, class T3, class T4, class T5, class T6>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5, T6 e6)
{
cerr << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << " " << e6
<< "\n";
}
template <class T1, class T2, class T3, class T4, class T5, class T6, class T7>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5, T6 e6, T7 e7)
{
cerr << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << " " << e6
<< " " << e7 << "\n";
}
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;
}
const int GRIDSIZE = 100002;
mt19937 rng((unsigned int)steady_clock::now().time_since_epoch().count());
struct Treap
{
private:
int key;
ll data, gcdVal;
unsigned int priority;
Treap *leftKid, *rightKid;
static void recalculate(Treap *node)
{
if (!node)
return;
node->gcdVal = gcd2(gcd2(node->data, getGcdVal(node->leftKid)), getGcdVal(node->rightKid));
}
static ll getGcdVal(Treap *node) { return node ? node->gcdVal : 0; }
static void print(Treap *node, bool &isFirst, bool isDebug)
{
if (!node)
return;
print(node->leftKid, isFirst, isDebug);
if (!isFirst)
{
if (isDebug)
cerr << " ";
else
cout << " ";
}
if (isDebug)
cerr << "(" << node->key << "," << node->data << ")";
else
cout << node->data;
isFirst = false;
print(node->rightKid, isFirst, isDebug);
return;
}
public:
Treap() : key(-1), data(0), gcdVal(0), priority(rng()), leftKid(nullptr), rightKid(nullptr) {}
Treap(int key, ll data) : key(key), data(data), gcdVal(data), priority(rng()), leftKid(nullptr), rightKid(nullptr) {}
static Treap *merge(Treap *l, Treap *r)
{
if (!l)
return r;
if (!r)
return l;
if (l->priority < r->priority)
{
l->rightKid = merge(l->rightKid, r);
recalculate(l);
return l;
}
else
{
r->leftKid = merge(l, r->leftKid);
recalculate(r);
return r;
}
}
static pair<Treap *, Treap *> split(Treap *node, int key)
{
if (!node)
return {nullptr, nullptr};
if (node->key <= key)
{
auto rightRes = split(node->rightKid, key);
node->rightKid = rightRes.first;
recalculate(node);
return {node, rightRes.second};
}
else
{
auto leftRes = split(node->leftKid, key);
node->leftKid = leftRes.second;
recalculate(node);
return {leftRes.first, node};
}
}
static void debug(Treap *node)
{
if (!node)
{
deb("nullptr", node);
return;
}
deb("in debug", node, node->key, node->data, node->priority);
}
static Treap *insertOrUpdate(Treap *node, int pos, ll val)
{
if (!node)
return new Treap(pos, val);
pair<Treap *, Treap *> firstSplit = split(node, pos - 1);
pair<Treap *, Treap *> secondSplit = split(firstSplit.second, pos);
Treap *target = secondSplit.first;
if (target && target->key == pos)
{
target->data = val;
recalculate(target);
}
else
{
target = new Treap(pos, val);
}
return merge(firstSplit.first, merge(target, secondSplit.second));
}
static ll rangeGcd(Treap *node, int l, int r)
{
if (l > r)
return 0;
pair<Treap *, Treap *> firstSplit = split(node, r);
pair<Treap *, Treap *> secondSplit = split(firstSplit.first, l - 1);
ll res = getGcdVal(secondSplit.second);
node = merge(merge(secondSplit.first, secondSplit.second), firstSplit.second);
return res;
}
static void print(Treap *node, bool isDebug = false)
{
bool isFirst = true;
print(node, isFirst, isDebug);
if (isDebug)
cerr << endl;
else
cout << endl;
return;
}
};
class TreapSegTree
{
public:
Treap *treap;
TreapSegTree *left, *right;
int N;
TreapSegTree() : N(0), treap(nullptr), left(nullptr), right(nullptr) {}
TreapSegTree(int n) : N(n), treap(nullptr), left(nullptr), right(nullptr) {}
private:
static TreapSegTree *update(TreapSegTree *node, int start, int end, int x, int y, ll value)
{
if (!node)
node = new TreapSegTree();
if (x < start || x > end)
return node;
if (start == end)
{
node->treap = Treap::insertOrUpdate(node->treap, y, value);
}
else
{
int mid = (start + end) / 2;
node->left = update(node->left, start, mid, x, y, value);
node->right = update(node->right, mid + 1, end, x, y, value);
node->treap = Treap::insertOrUpdate(node->treap, y, value);
}
return node;
}
static ll query(TreapSegTree *node, int start, int end, int l, int r, int q_start, int q_end)
{
if (!node || r < start || end < l)
return 0;
if (l <= start && end <= r)
{
return Treap::rangeGcd(node->treap, q_start, q_end);
}
int mid = (start + end) / 2;
ll leftGcdVal = query(node->left, start, mid, l, r, q_start, q_end);
ll rightGcdVal = query(node->right, mid + 1, end, l, r, q_start, q_end);
return gcd2(leftGcdVal, rightGcdVal);
}
public:
static TreapSegTree *pointUpdate(TreapSegTree *root, int x, int y, ll value)
{
if (!root)
return root;
return update(root, 1, root->N, x, y, value);
}
static ll rangeQuery(TreapSegTree *root, int x1, int y1, int x2, int y2)
{
if (!root)
return 0;
return query(root, 1, root->N, x1, x2, y1, y2);
}
};
TreapSegTree *sTree;
void init(int R, int C)
{
sTree = new TreapSegTree(R);
}
void update(int P, int Q, long long K)
{
P++;
Q++;
sTree = TreapSegTree::pointUpdate(sTree, P, Q, K);
}
long long calculate(int P, int Q, int U, int V)
{
P++;
Q++;
U++;
V++;
return TreapSegTree::rangeQuery(sTree, P, Q, U, V);
}
