// IOI 2013, Game
// Sparse Segment Tree + Splay Tree
// Test: https://oj.uz/submission/490590
#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 { // 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;
}
// Splay Tree base class.
// Works like map<K, V>, do not allow duplicate key.
template <typename K, typename V>
class SplayTree {
public:
struct Node {
K k;
V v;
int p = 0; // parent
int ch[2] = {0,0}; // child
};
vector<Node> a;
SplayTree(int init_capacity = 0) { Reset(init_capacity); }
void Reset(int init_capacity = 0) {
a.resize(1);
a[0] = null_node();
a.reserve(init_capacity + 1);
empty_idx.clear();
}
inline int Side(int u) { return a[a[u].p].ch[1] == u; }
int Splay(int u) {
assert(u > 0);
while (1) {
int pu = a[u].p;
if (!pu) break;
int ppu = a[pu].p;
if(ppu) {
if(Side(pu) == Side(u)) {
Rotate(pu);
} else {
Rotate(u);
}
}
Rotate(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 root = Splay(u);
}
if(a[u].k > k) {
u = a[u].ch[0];
} else {
u = a[u].ch[1];
}
}
return 0;
}
// Returns u that a[u].k is min.
int FindMin(int& root) {
if(!root) return 0;
int u=root;
while(a[u].ch[0]) u=a[u].ch[0];
return root=Splay(u);
}
// Returns u that a[u].k is max.
int FindMax(int& root) {
if(!root) return 0;
int u=root;
while(a[u].ch[1]) u=a[u].ch[1];
return root=Splay(u);
}
// Gets the prev node of root, or 0 if not present.
int Prev(int &root) {
int u = a[root].ch[0];
while (a[u].ch[1]) u = a[u].ch[1];
if (u) root = Splay(u);
return u;
}
// Gets the next node of root, or 0 if not present.
int Next(int &root) {
int u = a[root].ch[1];
while (a[u].ch[0]) u = a[u].ch[0];
if (u) root = Splay(u);
return u;
}
// Returns u that a[u].k is maximal and < k, or 0 not found.
int Prev(int& root, K k) {
bool insert_res = Insert(root, k);
int u = a[root].ch[0];
while (a[u].ch[1]) u = a[u].ch[1];
if (insert_res) assert(Delete(root, k));
if (u) root = Splay(u);
return u;
}
// Returns u that a[u].k is minimal and > k, or 0 not found.
int Next(int& root, K k) {
bool insert_res = Insert(root, k);
int u = a[root].ch[1];
while (a[u].ch[0]) u = a[u].ch[0];
if (insert_res) assert(Delete(root, k));
if (u) root = Splay(u);
return u;
}
// Returns false if the key already exists.
bool Insert(int& root, K k) {
int u = root;
int side = 0;
if (root) {
while (1) {
if (k == a[u].k) {
root = Splay(u);
return 0;
}
if (k < a[u].k) side=0; else side=1;
if(!a[u].ch[side]) break;
u = a[u].ch[side];
}
}
int v = NewNodeIdx();
InitNode(a[v], k);
if (root) {
a[u].ch[side] = v, a[v].p = u;
} else {
root=v;
}
root = Splay(v);
return 1;
}
// Merges two trees, all values of tree u must less than v.
// Returns new root.
int Merge(int u, int v) {
assert(!a[u].p);
assert(!a[v].p);
if(u==0) return v;
if(v==0) return u;
u=FindMax(u);
assert(!a[u].ch[1]);
a[u].ch[1]=v; a[v].p=u;
Maintain(u);
return u;
}
// Returns false if k doesn't exist.
bool Delete(int& root, K k) {
int u = Find(root, k);
if(!u) return 0;
int v0 = a[u].ch[0], v1 = a[u].ch[1];
a[v0].p = a[v1].p = 0;
empty_idx.pb(u);
root = Merge(v0, v1);
return 1;
}
void Debug() {
if (!dbg) return;
for(int u=1;u<SIZE(a);++u) {
/*
dpf("%d: %d, %d %d %d, %d %d\n",
u, a[u].k, a[u].p, a[u].ch[0], a[u].ch[1],
a[u].cnt, a[u].sz);
*/
}
}
protected:
inline virtual Node null_node() { return Node(); }
inline virtual void InitValue(Node& u) {}
inline virtual void Maintain(int u) {}
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;
}
void InitNode(Node& u, K k) {
u.k = k;
u.p = u.ch[0] = u.ch[1] = 0;
InitValue(u);
}
void Rotate(int u) {
int pu = a[u].p;
if (!pu) return;
int ppu = a[pu].p;
int uside = Side(u);
int uch = a[u].ch[uside ^ 1];
if (ppu) a[ppu].ch[Side(pu)] = u;
a[u].p = ppu;
a[pu].ch[uside] = uch, a[uch].p = pu;
a[u].ch[uside ^ 1] = pu, a[pu].p = u;
Maintain(pu);
Maintain(u);
}
};
// Splay Tree class, with weight and weight GCD-merge of sub-tree.
template <typename K, typename W>
class SplayTreeWithWeight : public SplayTree<K, pair<W, W>> {
public:
using T = pair<W, W>;
using Node = typename SplayTree<K, T>::Node;
void Set(int& root, K k, W w) {
bool insert_res = SplayTree<K, T>::Insert(root, k);
this->a[root].v.first = w;
Maintain(root);
}
protected:
inline virtual Node null_node() {
Node u;
u.v = {0, 0};
return u;
}
inline virtual void InitValue(Node& u) { u.v.first = u.v.second = 0; }
inline virtual void Maintain(int u) {
this->a[u].v.second = gcd2(gcd2(this->a[this->a[u].ch[0]].v.second,
this->a[this->a[u].ch[1]].v.second),
this->a[u].v.first);
}
};
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();
}
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;
SplayTreeWithWeight<int, i64> splay;
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;
splay.Reset();
}
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:
int Update(int x, int y, T v, int p, int li, int ri) {
if (p < 0) p = this->NewNode();
if (li == ri) {
splay.Set(a[p].v, y, v);
} else {
int m = (li + ri) >> 1;
if (x <= m) a[p].l = Update(x, y, v, a[p].l, li, m);
else a[p].r = Update(x, y, v, a[p].r, m + 1, ri);
T w = 0;
if (a[p].l >= 0) w = QueryY(a[a[p].l].v, y, y);
if (a[p].r >= 0) w = gcd2(w, QueryY(a[a[p].r].v, y, y));
splay.Set(a[p].v, y, w);
}
return p;
}
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) {
if (!root) return 0;
if (!splay.Next(root, qry)) {
if (!splay.Prev(root, qly)) return splay.a[root].v.second;
int root_r = splay.a[root].ch[1];
return root_r ? splay.a[root_r].v.second : 0;
}
int root_l = splay.a[root].ch[0];
if (!root_l) return 0;
splay.a[root_l].p = 0;
int u = splay.Prev(root_l, qly);
splay.a[root_l].p = root;
splay.a[root].ch[0] = root_l;
if (!u) return splay.a[root_l].v.second;
int root_lr = splay.a[root_l].ch[1];
return root_lr ? splay.a[root_lr].v.second : 0;
}
};
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);
}
