// IOI 2013, Game
// Sparse Segment Tree + Treap
// Test: https://www.luogu.com.cn/record/63941489
#include "game.h"
#include <algorithm>
#include <array>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
#ifdef DBG
#define dbg 1
#define dpf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#define Dps(...) Dbgs(__VA_ARGS__)
#else
#define dbg 0
#define dpf(...) 42
#define Dps(...) 42
#endif
#define SIZE(c) int((c).size())
#define FOR(i,l,r) for(int i = (l); i < (r); ++i)
#define REP(i,c) for(auto &i : (c))
#define ALL(c) (c).begin(),(c).end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
typedef long long i64;
typedef unsigned long long u64;
const double EPS = 1e-12;
const int INF = 1e9 + 10;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int, int> PI;
template <typename T> inline bool UpdateMax(T& x, T v) {
if(v > x) {x=v; return 1;} else return 0;
}
template <typename T> inline bool UpdateMin(T& x, T v) {
if(v < x) {x=v; return 1;} else return 0;
}
template <typename T>
using MinPQ = priority_queue<T, vector<T>, greater<T>>;
inline namespace output {
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& v) {
return os << "{" << v.first << " " << v.second << "}";
}
} // namespace output
inline namespace output { // Only for debug now.
template <class T>
void PrSep(std::ostream& os, string, const T& t) { os << t; }
template <class T, class... U>
void PrSep(std::ostream& os, string sep, const T& t, const U&... u) {
PrSep(os, sep, t); os << sep; PrSep(os, sep, u...);
}
// Print w/ spaces, end with newline
void Ps() { cout << "\n"; }
template<class ...T> void Ps(const T&... t) { PrSep(cout," ",t...); Ps(); }
template<class ...T> void Dbgs(const T&... t) { PrSep(cerr," ",t...); cerr << endl; }
} // namespace output
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 MAX_SEG_NODE = 2000000;
const int MAX_INNER_TREE_NODE = 4000000;
// Treap, Split/Merge, without rotation.
// Source: https://cp-algorithms.com/data_structures/treap.html
// Works like map<K, V>, do not allow duplicate key.
template <typename K, typename V>
class Treap {
public:
struct TrNode {
K k;
V v;
int pr = rand();
K min_k, max_k;
int l = 0, r = 0;
TrNode() {}
TrNode(K k, V v) : k(k), v(v) {
min_k = max_k = k;
}
};
vector<TrNode> a;
V identity;
inline virtual void Maintain(int u) {
if (a[u].l) a[u].min_k = min(a[u].k, a[a[u].l].min_k);
if (a[u].r) a[u].max_k = max(a[u].k, a[a[u].r].max_k);
}
void Init(V identity, int init_capacity = 0) {
this->identity = identity;
a.resize(1);
a[0] = TrNode();
a[0].v = identity;
a.reserve(init_capacity + 1);
empty_idx.clear();
}
void Split(int root, K k, int &l, int &r) {
if (!root) {
l = r = 0;
} else if (a[root].k <= k) {
Split(a[root].r, k, a[root].r, r);
l = root;
} else {
Split(a[root].l, k, l, a[root].l);
r = root;
}
if (l) Maintain(l);
if (r) Maintain(r);
}
// Merges two trees, all values of tree u must less than v.
// Returns new root.
int Merge(int l, int r) {
if (l == 0) return r;
if (r == 0) return l;
int u;
if (a[l].pr > a[r].pr) {
a[l].r = Merge(a[l].r, r);
u = l;
} else {
a[r].l = Merge(l, a[r].l);
u = r;
}
Maintain(u);
return u;
}
// Returns u that a[u].k == k, or 0 not found.
int Find(int root, K k) {
int u = root;
while (u) {
if (a[u].k == k) return u;
if (a[u].k > k)
u = a[u].l;
else
u = a[u].r;
}
return 0;
}
// If the key already exists, returns {the existing node, false}.
// Otherwise, returns {the newly inserted node, true}, the value of the
// newly inserted node will be `identity`.
pair<int, bool> Insert(int& root, K k) {
int u = Find(root, k);
if (u) return {u, false};
u = NewNodeIdx();
a[u] = TrNode(k, identity);
int l, r;
Split(root, k, l, r);
root = Merge(Merge(l, u), r);
return {u, true};
}
void MaintainFromRoot(int root, int u) {
if (a[u].k < a[root].k)
MaintainFromRoot(a[root].l, u);
else if (a[u].k > a[root].k)
MaintainFromRoot(a[root].r, u);
Maintain(root);
}
friend std::ostream& operator<<(std::ostream& os, const Treap<K, V>& t) {
for (int i = 1; i < SIZE(t.a); ++i) {
os << i << ": {" << t.a[i].k << " " << t.a[i].v << "} " << t.a[i].pr
<< " {" << t.a[i].l << " " << t.a[i].r << "}\n";
}
return os;
}
private:
VI empty_idx;
int NewNodeIdx() {
int u;
if (!empty_idx.empty()) {
u = empty_idx.back();
empty_idx.pop_back();
} else {
u = SIZE(a);
a.emplace_back();
}
return u;
}
};
// Treap, with weight and weight GCD-merge of sub-tree.
class TreapWithWeight : public Treap<int, pair<i64, i64>> {
public:
using K = int;
using T = pair<i64, i64>;
using Base = Treap<K, T>;
using TrNode = typename Base::TrNode;
void Init() {
Base::Init({0, 0}, MAX_INNER_TREE_NODE);
}
inline virtual void Maintain(int u) {
Base::Maintain(u);
a[u].v.second = gcd2(gcd2(a[a[u].l].v.second, a[a[u].r].v.second),
a[u].v.first);
}
void Set(int& root, K k, i64 w) {
int u = Base::Insert(root, k).first;
a[u].v.first = w;
Base::MaintainFromRoot(root, u);
}
i64 RangeQuery(int root, K min_k, K max_k) {
i64 res = 0;
if (!root || a[root].max_k < min_k || a[root].min_k > max_k)
;
else if (a[root].min_k >= min_k && a[root].max_k <= max_k)
res = a[root].v.second;
else {
if (a[root].k >= min_k && a[root].k <= max_k) res = a[root].v.first;
res = gcd2(res, RangeQuery(a[root].l, min_k, max_k));
res = gcd2(res, RangeQuery(a[root].r, min_k, max_k));
}
return res;
}
};
template <typename T>
class BaseDySegTree {
public:
struct Node {
int l = -1, r = -1;
T v;
};
int max_idx;
vector<Node> a;
inline virtual T default_value() const = 0;
void Init(int max_idx) {
assert(max_idx >= -1);
this->max_idx = max_idx;
a.clear();
a.reserve(MAX_SEG_NODE);
}
int NewNode() {
int res = SIZE(a);
a.emplace_back();
a.back().v = default_value();
return res;
}
};
template <typename T>
class DySegTree2D : public BaseDySegTree<int> {
public:
int max_y;
TreapWithWeight tree;
inline virtual int default_value() const { return 0; }
void Init(int max_x, int max_y) {
BaseDySegTree<int>::Init(max_x);
this->max_y = max_y;
tree.Init();
}
int Update(int x, int y, T v, int p) { return Update(x, y, v, p, 0, this->max_idx); }
T Query(int qlx, int qrx, int qly, int qry, int p) {
return Query(qlx, qrx, qly, qry, p, 0, this->max_idx);
}
private:
inline void NewLeft(int p) {
if (a[p].l < 0) a[p].l = NewNode();
}
inline void NewRight(int p) {
if (a[p].r < 0) a[p].r = NewNode();
}
T Update(int x, int y, T v, int p, int li, int ri) {
T res;
if (li == ri) {
res = v;
} else {
int m = (li + ri) >> 1;
if (x <= m) {
NewLeft(p);
res = Update(x, y, v, a[p].l, li, m);
if (a[p].r >= 0) res = gcd2(res, QueryY(a[a[p].r].v, y, y));
} else {
NewRight(p);
res = Update(x, y, v, a[p].r, m + 1, ri);
if (a[p].l >= 0) res = gcd2(res, QueryY(a[a[p].l].v, y, y));
}
}
tree.Set(a[p].v, y, res);
return res;
}
T Query(int qlx, int qrx, int qly, int qry, int p, int lx, int rx) {
if (p < 0 || qlx > rx || qrx < lx) return 0;
T res;
if (qlx <= lx && qrx >= rx) {
res = QueryY(a[p].v, qly, qry);
} else {
int m = (lx + rx) >> 1;
res = gcd2(Query(qlx, qrx, qly, qry, this->a[p].l, lx, m),
Query(qlx, qrx, qly, qry, this->a[p].r, m + 1, rx));
}
return res;
}
T QueryY(int root, int qly, int qry) {
return tree.RangeQuery(root, qly, qry);
}
};
DySegTree2D<i64> st;
int root;
void init(int R, int C) {
st.Init(R - 1, C - 1);
root = st.NewNode();
}
void update(int x, int y, i64 w) {
st.Update(x, y, w, root);
}
i64 calculate(int lx, int ly, int rx, int ry) {
return st.Query(lx, rx, ly, ry, root);
}
