#include "game.h"
#include <bits/stdc++.h>
using namespace std;
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 Node {
int key, priority;
long long val, ans;
Node *l, *r;
Node(int _key, long long _val) : key(_key), priority(rand() + (rand() << 15)), val(_val), ans(_val), l(NULL), r(NULL) {}
};
typedef Node* pNode;
long long ans(pNode t) {
return t ? t->ans : 0;
}
void pull(pNode t) {
if (t) t->ans = gcd2(gcd2(ans(t->l), ans(t->r)), t->val);
}
void split(pNode t, int key, pNode &l, pNode &r) {
if (!t)
l = r = NULL;
else if (key < t->key)
split(t->l, key, l, t->l), r = t;
else
split(t->r, key, t->r, r), l = t;
pull(t);
}
void merge(pNode &t, pNode l, pNode 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;
pull(t);
}
long long query(pNode t, int l, int r) {
pNode pl, pm, pr;
split(t, l-1, pl, pm);
split(pm, r, t, pr);
long long ret = ans(t);
merge(pm, pl, t);
merge(t, pm, pr);
return ret;
}
void update(pNode &t, int p, long long val) {
pNode pl, pm, pr;
split(t, p-1, pl, pm);
split(pm, p, t, pr);
if (t) t->val = t->ans = val;
else t = new Node(p, val);
merge(pm, pl, t);
merge(t, pm, pr);
}
struct Seg {
pNode node;
Seg *l, *r;
Seg() : node(NULL), l(NULL), r(NULL) {}
};
int n, _r;
long long query(Seg *p, int l, int r, int ix, int iy, int jx, int jy) {
if (ix > r || jx < l || !p)
return 0;
if (ix <= l && r <= jx)
return query(p->node, iy, jy);
int m = (l + r) / 2;
return gcd2(query(p->l, l, m, ix, iy, jx, jy), query(p->r, m+1, r, ix, iy, jx, jy));
}
void update(Seg *p, int l, int r, int x, int y, long long val) {
if (l == r) {
update(p->node, y, val);
return;
}
int m = (l + r) / 2;
if (x <= m) {
if (!p->l) p->l = new Seg();
update(p->l, l, m, x, y, val);
} else {
if (!p->r) p->r = new Seg();
update(p->r, m+1, r, x, y, val);
}
update(p->node, y, gcd2(p->l ? query(p->l->node, y, y) : 0, p->r ? query(p->r->node, y, y) : 0));
}
Seg st;
void init(int R, int C) {
n = C;
_r = R;
}
void update(int P, int Q, long long K) {
update(&st, 0, _r-1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return query(&st, 0, _r-1, P, Q, U, V);
}
