#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 SegmentTreeInside {
struct NodeInside {
lint val;
NodeInside *lc, *rc;
NodeInside(): val(0), lc(NULL), rc(NULL) {}
};
NodeInside *root;
SegmentTreeInside() { root = new NodeInside(); }
void update(NodeInside *n, int tl, int tr, int p, lint x) {
if (tl == tr) {
n->val = x;
return;
}
int mid = (tl + tr) / 2;
if (n->lc == NULL && p <= mid) n->lc = new NodeInside();
if (n->rc == NULL && p > mid) n->rc = new NodeInside();
if (p <= mid)
update(n->lc, tl, mid, p, x);
else
update(n->rc, mid + 1, tr, p, x);
n->val = gcd((n->lc)? n->lc->val : 0, (n->rc)? n->rc->val : 0);
}
lint query(NodeInside *n, int tl, int tr, int le, int ri) {
if (tr < le || tl > ri || tl > tr) return 0;
if (le <= tl && tr <= ri) return n->val;
int mid = (tl + tr) / 2;
lint gcd1 = (n->lc)? query(n->lc, tl, mid, le, ri) : 0;
lint gcd2 = (n->rc)? query(n->rc, mid + 1, tr, le, ri) : 0;
return gcd(gcd1, gcd2);
}
};
struct SegmentTree {
struct Node {
SegmentTreeInside *seg;
Node *lc, *rc;
Node() { lc = rc = NULL; seg = NULL; }
};
Node *root;
SegmentTree() { root = new Node(); }
void update(Node *n, int tl, int tr, int p, int q, lint x) {
if (tl == tr) {
if (n->seg == NULL) n->seg = new SegmentTreeInside();
n->seg->update(n->seg->root, 0, C - 1, q, x);
return;
}
int mid = (tl + tr) / 2;
if (n->lc == NULL && p <= mid) n->lc = new Node();
if (n->rc == NULL && p > mid) n->rc = new Node();
if (n->seg == NULL && x > 0) n->seg = new SegmentTreeInside();
if (p <= mid)
update(n->lc, tl, mid, p, q, x);
else
update(n->rc, mid + 1, tr, p, q, x);
lint gcd1 = (n->lc && n->lc->seg)? n->lc->seg->query(n->lc->seg->root, 0, C - 1, q, q) : 0;
lint gcd2 = (n->rc && n->rc->seg)? n->rc->seg->query(n->rc->seg->root, 0, C - 1, q, q) : 0;
if (n->seg) n->seg->update(n->seg->root, 0, C - 1, q, gcd(gcd1, gcd2));
}
lint query(Node *n, lint tl, lint tr, lint le, lint ri, lint lo, lint hi) {
if (tr < le || tl > ri || tl > tr) return 0;
if (le <= tl && tr <= ri) {
return (n->seg)? n->seg->query(n->seg->root, 0, C - 1, lo, hi) : 0;
}
int mid = (tl + tr) / 2;
lint gcd1 = (n->lc)? query(n->lc, tl, mid, le, ri, lo, hi) : 0;
lint gcd2 = (n->rc)? query(n->rc, mid + 1, tr, le, ri, lo, hi) : 0;
return gcd(gcd1, gcd2);
}
};
SegmentTree solver;
void init(int R, int C) {
::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);
}
