#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;
}
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;
inline virtual void CombineNode(const T& lv, const T& rv, T& v) = 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;
}
T Query(int qli, int qri, int p) {
return Query(qli, qri, p, 0, this->max_idx);
}
protected:
// Combines left and right children to current node.
inline void PushUp(int p) {
CombineNode(
(a[p].l < 0) ? default_value() : a[a[p].l].v,
(a[p].r < 0) ? default_value() : a[a[p].r].v,
a[p].v);
}
private:
T Query(int qli, int qri, int p, int li, int ri) {
T res;
if (p < 0 || qli > ri || qri < li) res = default_value();
else if (qli <= li && qri >= ri) {
res = this->a[p].v;
} else {
int m = (li + ri) >> 1;
CombineNode(Query(qli, qri, this->a[p].l, li, m),
Query(qli, qri, this->a[p].r, m + 1, ri), res);
}
return res;
}
};
template <typename T>
class DySegTree : public BaseDySegTree<T> {
public:
inline virtual T default_value() const { return 0; }
inline virtual void CombineNode(const T& lv, const T& rv, T& v) {
v = gcd2(lv, rv);
}
int Set(int i, T v, int p) { return Set(i, v, p, 0, this->max_idx); }
private:
int Set(int i, T v, int p, int li, int ri) {
if (p < 0) p = this->NewNode();
if (li == ri) {
this->a[p].v = v;
} else {
int m = (li + ri) >> 1;
if (i <= m) this->a[p].l = Set(i, v, this->a[p].l, li, m);
else this->a[p].r = Set(i, v, this->a[p].r, m + 1, ri);
this->PushUp(p);
}
return p;
}
};
template <typename T>
class DySegTree2D : public BaseDySegTree<int> {
public:
DySegTree<T> y_st;
inline virtual int default_value() const { return -1; }
void Init(int max_x, int max_y) {
BaseDySegTree<int>::Init(max_x);
y_st.Init(max_y);
}
int Set(int x, int y, T v, int p) { return Set(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);
}
protected:
inline virtual void CombineNode(const int& lv, const int& rv, int& v) {}
inline void PushUp(int p) {}
private:
int Set(int x, int y, T v, int p, int li, int ri) {
if (p < 0) p = NewNode();
a[p].v = y_st.Set(y, v, a[p].v);
if (li < ri) {
int m = (li + ri) >> 1;
if (x <= m) a[p].l = Set(x, y, v, a[p].l, li, m);
else a[p].r = Set(x, y, v, a[p].r, m + 1, ri);
}
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 y_st.default_value();
T res;
if (qlx <= lx && qrx >= rx) {
res = y_st.Query(qly, qry, a[p].v);
} else {
int m = (lx + rx) >> 1;
y_st.CombineNode(Query(qlx, qrx, qly, qry, this->a[p].l, lx, m),
Query(qlx, qrx, qly, qry, this->a[p].r, m + 1, rx), res);
}
return res;
}
};
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.Set(x, y, w, root);
}
i64 calculate(int lx, int ly, int rx, int ry) {
return st.Query(lx, rx, ly, ry, root);
}
