#include "game.h"
#include <bits/stdc++.h>
typedef long long ll;
const ll size = 1073741824;
// ew begin //
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;
}
// ew end //
struct Node {
ll va, in;
Node* ln, * rn;
Node(ll VAL = 0, ll IND = 0) : va(VAL), in(IND), ln(nullptr), rn(nullptr) { }
~Node() {
if (ln) delete(ln);
if (rn) delete(rn);
}
void set(ll ind, ll val, ll l, ll r) {
if (!(r - l - 1LL)) {
va = val;
return;
}
ll mid = (l + r) >> 1LL;
if (ind < mid) {
if (!ln) ln = new Node(0, in * 2LL + 1LL);
ln->set(ind, val, l, mid);
} else {
if (!rn) rn = new Node(0, in * 2LL + 2LL);
rn->set(ind, val, mid, r);
}
ll newv = 0;
if (ln) newv = gcd2(newv, ln->va);
if (rn) newv = gcd2(newv, rn->va);
va = newv;
}
ll get(ll tl, ll tr, ll l, ll r) {
if (l >= tr || r <= tl) return 0;
if (l >= tl && r <= tr) return va;
ll mid = (l + r) >> 1LL;
ll re = 0;
if (ln) re = gcd2(re, ln->get(tl, tr, l, mid));
if (rn) re = gcd2(re, rn->get(tl, tr, mid, r));
return re;
}
};
struct SNode {
ll in;
Node* node;
SNode* ln, * rn;
SNode(ll IND = 0) : in(IND), node(new Node), ln(nullptr), rn(nullptr) { }
~SNode() {
if (node) delete(node);
if (ln) delete(ln);
if (rn) delete(rn);
}
void merge(Node* l, Node* r, Node* t) {
if (!l && !r) return;
ll vl = 0;
if (l) vl = gcd2(vl, l->va);
if (r) vl = gcd2(vl, r->va);
t->va = vl;
if ((l && l->ln) || (r && r->ln)) {
if (!t->ln) t->ln = new Node(0, t->in * 2LL + 1LL);
merge(l ? l->ln : nullptr, r ? r->ln : nullptr, t->ln);
}
if ((l && l->rn) || (r && r->rn)) {
if (!t->rn) t->rn = new Node(0, t->in * 2LL + 2LL);
merge(l ? l->rn : nullptr, r ? r->rn : nullptr, t->rn);
}
}
void set(ll ind, ll nind, ll val, ll l, ll r) {
if (!(r - l - 1LL)) {
node->set(nind, val, 0, size);
return;
}
ll mid = (l + r) >> 1LL;
if(ind < mid) {
if (!ln) ln = new SNode(in * 2LL + 1LL);
ln->set(ind, nind, val, l, mid);
} else {
if (!rn) rn = new SNode(in * 2LL + 2LL);
rn->set(ind, nind, val, mid, r);
}
merge(ln ? ln->node : nullptr, rn ? rn->node : nullptr, node);
}
ll get(ll tl, ll tr, ll ntl, ll ntr, ll l, ll r) {
if (l >= tr || r <= tl) return 0;
if (l >= tl && r <= tr) return node->get(ntl, ntr, 0, size);
ll mid = (l + r) >> 1LL;
ll re = 0;
if (ln) re = gcd2(re, ln->get(tl, tr, ntl, ntr, l, mid));
if (rn) re = gcd2(re, rn->get(tl, tr, ntl, ntr, mid, r));
return re;
}
};
SNode* head = new SNode;
void init(int r, int c) { /* imagine needing it */ }
void update(int r, int c, ll val) { head->set(r, c, val, 0, size); }
ll calculate(int r1, int c1, int r2, int c2) { return head->get(r1, r2 + 1, c1, c2 + 1, 0, size); }
