#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;
typedef vector<ll> vl;
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;
}
struct segtree1 {
struct node1 {
ll fr, to;
ll val;
node1 * leCh;
node1 * riCh;
node1 (ll _fr, ll _to) {
fr = _fr;
to = _to;
val = 0;
leCh = riCh = nullptr;
}
void upd () {
ll mid = (fr+to)/2;
if (!leCh)
leCh = new node1 (fr, mid);
if (!riCh)
riCh = new node1 (mid+1, to);
}
};
void upd (ll p, ll newVal, node1 * cur) {
if (cur->fr == cur->to){
cur->val = newVal;
return;
}
ll mid = (cur->fr) + (cur->to);
mid /= 2;
cur->upd();
if (p <= mid)
upd(p, newVal, cur->leCh);
else
upd (p, newVal, cur->riCh);
cur->val = gcd2(cur->leCh->val, cur->riCh->val);
}
ll get(ll rfr, ll rto, node1 * cur) {
if (rfr > (cur->to) || rto < (cur->fr)) return 0;
if (rfr <= (cur->fr) && (cur->to) <= rto) return cur->val;
if (!(cur->leCh)) return 0;
cur->upd();
return gcd2(get(rfr, rto, cur->leCh), get(rfr, rto, cur->riCh));
}
node1 * root = new node1 (0, 1e9);
void upd (ll pos, ll newVal) {
upd(pos, newVal, root);
}
ll get (ll fr, ll to) {
return get(fr, to, root);
}
};
struct segtree2 {
struct node2 {
ll fr, to;
segtree1 * tr;
node2 * leCh;
node2 * riCh;
node2 (ll _fr, ll _to) {
fr = _fr;
to = _to;
tr = new segtree1();
leCh = riCh = nullptr;
}
void upd () {
ll mid = (fr+to)/2;
if (!leCh)
leCh = new node2 (fr, mid);
if (!riCh)
riCh = new node2 (mid+1, to);
}
};
ll get(ll frx, ll tox, ll fry, ll toy, node2 * cur) {
if (frx > (cur->to) || tox < (cur->fr)) {
// cout << " in get, discard frx = " << frx << " tox = " << tox << "fry = " << fry
//<< " toy = " << toy << " cur: [" << cur->fr << ", " << cur->to << "]" << endl;
return 0;
}
if (frx <= (cur->fr) && (cur->to) <= tox) {
ll ret = cur->tr->get(fry, toy);
// cout << " in get, frx = " << frx << " tox = " << tox << "fry = " << fry
// << " toy = " << toy << " cur: [" << cur->fr << ", " << cur->to << "]" << endl;
// cout << " returnin ret = " << ret << endl;
return ret;
}
if (!(cur->leCh)) return 0;
//cur->upd();
ll ret = gcd2(get(frx, tox, fry, toy, cur->leCh), get(frx, tox, fry, toy, cur->riCh));
// cout << " in get, frx = " << frx << " tox = " << tox << "fry = " << fry
// << " toy = " << toy << " cur: [" << cur->fr << ", " << cur->to << "]" << endl;
//cout << " returning ret = " << ret << endl;
return ret;
}
void upd (ll px, ll py, ll newVal, node2 * cur) {
if (cur->fr == cur->to){
// cout << " in upd, cur [" << cur->fr << ", " << cur->to << "], py = " << py << " newVal = " << newVal << endl;
cur->tr->upd(py, newVal);
return;
}
ll mid = (cur->fr) + (cur->to);
mid /= 2;
cur->upd();
if (px <= mid)
upd(px, py, newVal, cur->leCh);
else
upd (px, py, newVal, cur->riCh);
// cur->val = gcd2(cur->leCh->val, cur->riCh->val);
ll g = gcd2(get(cur->fr, mid, py, py, cur->leCh), get(mid+1, cur->to, py, py, cur->riCh));
cur->tr->upd (py, g);
// cout << " in upd, cur [" << cur->fr << ", " << cur->to << "], py = " << py << " g = " << g << endl;
}
node2 * root = new node2 (0, 1e9);
void upd (ll posx, ll posy, ll newVal) {
upd(posx, posy, newVal, root);
}
ll get (ll frx, ll fry, ll tox, ll toy) {
return get(frx, fry, tox, toy, root);
}
};
segtree2 tree;
void init(int R, int C) {
}
void update(int P, int Q, long long K) {
tree.upd(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
//cout << "------------------doing get" << endl;
ll ans = tree.get(P, U, Q, V);
//cout << "---------------------after get" << endl;
return ans;
}
