#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
int R, C;
inline lint gcd(lint X, lint Y) {
lint tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct Treap {
struct TreapNode {
lint val, real_val;
int key, priority;
int tl, tr;
TreapNode *l, *r;
TreapNode(): val(0), real_val(0), key(-1), tl(0), tr(0), l(NULL), r(NULL), priority(rand()) {}
TreapNode(int k, lint v): key(k), real_val(v), val(v), tl(k), tr(k), l(NULL), r(NULL), priority(rand()) {}
inline void update() {
val = real_val;
if (l) val = gcd(val, l->val);
if (r) val = gcd(val, r->val);
tl = l ? l->tl : key;
tr = r ? r->tr : key;
}
};
using node = TreapNode *;
node root;
Treap(): root(NULL) {}
void split(node t, node &l, node &r, int key) {
if (!t)
l = r = NULL;
else if (key < t->key)
split(t->l, l, t->l, key), r = t;
else
split(t->r, t->r, r, key), l = t;
if (t) t->update();
}
void merge(node &t, node l, node r) {
if (!l || !r)
t = (l)? l : r;
else if (l->priority > r->priority)
merge(l->r, l->r, r), t = l;
else
merge(r->l, l, r->l), t = r;
if (t) t->update();
}
bool find(int key) {
node t = root;
while (t) {
if (t->key == key) return true;
t = (key < t->key)? t->l : t->r;
}
return false;
}
void update(node t, int key, lint val) {
if (t->key == key)
t->real_val = val;
else
update((key < t->key)? t->l : t->r, key, val);
if (t) t->update();
}
void insert(int pos, lint val) {
if (find(pos)) return void(update(root, pos, val));
node l, r;
split(root, l, r, pos);
merge(l, l, new TreapNode(pos, val));
merge(root, l, r);
}
lint query(node t, int le, int ri) {
if (!t || le > t->tr || ri < t->tl) return 0;
if (le <= t->tl && t->tr <= ri) return t->val;
lint res = (le <= t->key && t->key <= ri)? t->real_val : 0;
res = gcd(res, query(t->l, le, ri));
res = gcd(res, query(t->r, le, ri));
return res;
}
inline lint query(int l, int r) {
return query(root, l, r);
}
};
struct SegmentTree {
struct SegmentTreeNode {
Treap treap;
SegmentTreeNode *lc, *rc;
SegmentTreeNode() { lc = rc = NULL; }
};
using node = SegmentTreeNode *;
node root;
SegmentTree() { root = new SegmentTreeNode(); }
void update(node n, int tl, int tr, int p, int q, lint x) {
if (tl == tr) return void(n->treap.insert(q, x));
if (n->lc == NULL) n->lc = new SegmentTreeNode();
if (n->rc == NULL) n->rc = new SegmentTreeNode();
int mid = (tl + tr) / 2;
if (p <= mid) update(n->lc, tl, mid, p, q, x);
if (p > mid) update(n->rc, mid + 1, tr, p, q, x);
lint gcd1 = n->lc->treap.query(q, q);
lint gcd2 = n->rc->treap.query(q, q);
n->treap.insert(q, gcd(gcd1, gcd2));
}
lint query(node n, int tl, int tr, int le, int ri, int lo, int hi) {
if (!n || tr < le || tl > ri || tl > tr) return 0;
if (le <= tl && tr <= ri) return n->treap.query(lo, hi);
int mid = (tl + tr) / 2;
lint gcd1 = query(n->lc, tl, mid, le, ri, lo, hi);
lint gcd2 = query(n->rc, mid + 1, tr, le, ri, lo, hi);
return gcd(gcd1, gcd2);
}
};
SegmentTree solver;
void init(int R, int C) {
srand(time(NULL));
::R = R, ::C = C;
}
void update(int P, int Q, lint K) {
solver.update(solver.root, 0, R - 1, P, Q, K);
}
lint calculate(int P, int Q, int U, int V) {
return solver.query(solver.root, 0, R - 1, P, U, Q, V);
}
