#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int N, M;
long long inf;
long long gcd2(long long X, long long Y) {
long long tmp;
while ( Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
long long coord(int x, int y) {
return 1LL * (y - 1) * N + x;
}
struct Treap {
Treap* left;
Treap* right;
long long prio, pos, val, gcd;
};
Treap* emptyTreap = new Treap {NULL, NULL, 0LL, 0LL, 0LL, 0LL};
void recompute(Treap* root) {
if (root != emptyTreap)
root->gcd = gcd2(gcd2(root->left->gcd, root->right->gcd), root->val);
}
pair<Treap*, Treap*> split(Treap* root, long long pos) {
if (root == emptyTreap)
return {emptyTreap, emptyTreap};
pair<Treap*, Treap*> ans;
if (root->pos <= pos) {
ans.first = root;
pair<Treap*, Treap*>aux = split(root->right, pos);
ans.second = aux.second;
ans.first->right = aux.first;
recompute(ans.first);
} else {
ans.second = root;
pair<Treap*, Treap*>aux = split(root->left, pos);
ans.first = aux.first;
ans.second->left = aux.second;
recompute(ans.second);
}
return ans;
}
Treap* join(Treap* a, Treap* b) {
if (a == emptyTreap)
return b;
if (b == emptyTreap)
return a;
if (a->prio < b->prio) {
a->right = join(a->right, b);
recompute(a);
return a;
} else {
b->left = join(a, b->left);
recompute(b);
return b;
}
}
Treap* TreapUpdate(Treap* root, long long pos, long long val) {
pair<Treap*, Treap*>aux1 = split(root, pos - 1);
pair<Treap*, Treap*>aux2 = split(aux1.second, pos);
Treap* newTreap = new Treap {emptyTreap, emptyTreap, ((long long)rand() << 31) ^ rand(), pos, val, val};
return join(join(aux1.first, newTreap), aux2.second);
}
long long TreapQuery(Treap* root, long long l, long long r, long long p, long long q) {
if (root == emptyTreap)
return 0;
long long ans = 0;
if (p <= root->pos && root->pos <= q) {
ans = root->val;
if (l >= p)
ans = gcd2(ans, root->left->gcd);
else
ans = gcd2(ans, TreapQuery(root->left, l, root->pos, p, q));
if (r <= q)
ans = gcd2(ans, root->right->gcd);
else
ans = gcd2(ans, TreapQuery(root->right, root->pos, r, p, q));
} else {
if (p > root->pos)
ans = TreapQuery(root->right, root->pos, r, p, q);
else
ans = TreapQuery(root->left, l, root->pos, p, q);
}
return ans;
}
struct SegTree {
Treap* treap;
SegTree* left;
SegTree* right;
};
SegTree* emptyTree = new SegTree {emptyTreap, NULL, NULL};
SegTree* Root;
SegTree* SegTreeUpdate(SegTree* root, int l, int r, int P, int Q, long long pos, long long K) {
if (root == emptyTree)
root = new SegTree {emptyTreap, emptyTree, emptyTree};
root->treap = TreapUpdate(root->treap, pos, K);
if (l == r)
return root;
int mid = (l + r) / 2;
if (P <= mid)
root->left = SegTreeUpdate(root->left, l, mid, P, Q, pos, K);
else
root->right = SegTreeUpdate(root->right, mid + 1, r, P, Q, pos, K);
return root;
}
long long SegTreeQuery(SegTree* root, int l, int r, int P, int Q, int U, int V, long long pos1, long long pos2) {
if (U < l)
return 0;
if (r < P)
return 0;
if (root == emptyTree)
return 0;
if (P <= l && r <= U)
return TreapQuery(root->treap, 0, inf, pos1, pos2);
int mid = (l + r) / 2;
return gcd2(SegTreeQuery(root->left, l, mid, P, Q, U, V, pos1, pos2), SegTreeQuery(root->right, mid + 1, r, P, Q, U, V, pos1, pos2));
}
void init(int R, int C) {
srand(time(NULL));
Root = emptyTree;
N = R;
M = C;
inf = coord(N, M) + 1;
}
void update(int P, int Q, long long K) {
Root = SegTreeUpdate(Root, 1, N, P + 1, Q + 1, coord(P + 1, Q + 1), K);
}
long long calculate(int P, int Q, int U, int V) {
return SegTreeQuery(Root, 1, N, P + 1, Q + 1, U + 1, V + 1, coord(P + 1, Q + 1), coord(U + 1, V + 1));
}
