#include "game.h"
#include<bits/stdc++.h>
using namespace std;
template<typename A, typename B>
string to_string(pair<A, B>);
string to_string(string s) {
return '"' + s + '"';
}
string to_string(char c) {
return "'"s + c + "'";
}
string to_string(const char* c) {
return to_string(string(c));
}
string to_string(bool b) {
return (b ? "true" : "false");
}
template<size_t T>
string to_string(bitset<T> bs) {
return bs.to_string();
}
string to_string(vector<bool> v) {
string res = "{";
for (int i = 0; i < int(v.size()); ++i) {
if (int(res.size()) > 1) {
res += ", ";
}
res += to_string(v[i]);
}
res += "}";
return res;
}
template<typename T>
string to_string(T v) {
string res = "{";
for (auto x : v) {
if (int(res.size()) > 1) {
res += ", ";
}
res += to_string(x);
}
res += "}";
return res;
}
template<typename A, typename B>
string to_string(pair<A, B> p) {
return '(' + to_string(p.first) + ", " + to_string(p.second) + ')';
}
void debug_out() {
cerr << endl;
}
template<typename H, typename... T>
void debug_out(H head, T... tail) {
cerr << " " << to_string(head);
debug_out(tail...);
}
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]", debug_out(__VA_ARGS__)
#else
#define debug(...) void(37)
#endif
const int MAX = int(1e9); //temp
//#define debug(...) void(37)
struct GcdSegTree {
struct node {
long long g = 0;
node* l = NULL;
node* r = NULL;
int jump = -1;
};
void pull(node* v) {
v->g = 0;
if (v->l != NULL) {
v->g = gcd(v->g, v->l->g);
}
if (v->r != NULL) {
v->g = gcd(v->g, v->r->g);
}
}
bool J(node* v) const {
return (v->l == NULL && v->r == NULL && v->jump != -1);
}
node* root;
GcdSegTree() {
root = new node();
}
node* modify(node* v, int l, int r, int p, long long g) {
debug(l, r, p, g);
if (v == NULL || (J(v) && p == v->jump)) {
v = new node();
v->g = g;
v->jump = p;
debug("created");
return v;
}
if (l == r) {
v->g = g;
return v;
}
bool branch = J(v);
int mid = (l + r) >> 1;
if (p <= mid) {
v->l = modify(v->l, l, mid, p, g);
} else {
v->r = modify(v->r, mid + 1, r, p, g);
}
//assert(!J(v));
if (branch) {
debug("branch");
modify(v, l, r, v->jump, v->g);
} else {
pull(v);
}
debug(l, r, v->g);
return v;
}
long long get(node* v, int l, int r, int ll, int rr) const {
if (J(v)) {
l = r = v->jump;
}
debug(l, r, ll, rr, v->g);
if (l >= ll && rr >= r) {
return v->g;
}
int mid = (l + r) >> 1;
long long res = 0;
if (mid >= ll && v->l != NULL) {
res = gcd(res, get(v->l, l, mid, ll, rr));
}
if (mid < rr && v->r != NULL) {
res = gcd(res, get(v->r, mid + 1, r, ll, rr));
}
return res;
}
long long get(int l, int r) const {
return get(root, 0, MAX - 1, l, r);
}
void modify(int p, long long x) {
//debug(p, x);
modify(root, 0, MAX - 1, p, x);
}
};
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]", debug_out(__VA_ARGS__)
#else
#define debug(...) void(37)
#endif
struct TwoDSegTree {
struct node {
GcdSegTree st;
node* l = NULL;
node* r = NULL;
};
//add jump to this too if it gets tle or some shit
node* root;
map<int, GcdSegTree> cols;
TwoDSegTree() {
root = new node();
}
long long get(node* v, int l, int r, int rl, int rr, int cl, int cr) {
debug(l, r, rl, rr, cl, cr);
if (l >= rl && rr >= r) {
return v->st.get(cl, cr);
}
int mid = (l + r) >> 1;
long long res = 0;
if (mid >= rl && v->l != NULL) {
res = gcd(res, get(v->l, l, mid, rl, rr, cl, cr));
}
if (mid < rr && v->r != NULL) {
res = gcd(res, get(v->r, mid + 1, r, rl, rr, cl, cr));
}
return res;
}
node* modify(node* v, int l, int r, int row, int col, const GcdSegTree& carry) {
if (v == NULL) {
v = new node();
}
long long upd = carry.get(l, r);
debug("2D", l, r, upd);
v->st.modify(col, upd);
if (l < r) {
int mid = (l + r) >> 1;
if (row <= mid) {
v->l = modify(v->l, l, mid, row, col, carry);
} else {
v->r = modify(v->r, mid + 1, r, row, col, carry);
}
}
return v;
}
long long get(int rl, int rr, int cl, int cr) {
return get(root, 0, MAX - 1, rl, rr, cl, cr);
}
void modify(int row, int col, long long x) {
cols[col].modify(row, x);
modify(root, 0, MAX - 1, row, col, cols[col]);
}
};
TwoDSegTree st;
void init(int R, int C) {
}
void update(int P, int Q, long long K) {
debug("asdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasdasd", P, Q, K);
st.modify(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return st.get(P, U, Q, V);
}
