#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int N, M;
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;
}
long long coord(int x, int y) {
return 1LL * (y - 1) * N + x;
}
struct Treap {
Treap* left;
Treap* right;
int sz, prio;
long long pos, val, gcd;
};
Treap* emptyTreap = new Treap {NULL, NULL, 0, 0, 0LL, 0LL, 0LL};
void recompute(Treap* root) {
if (root != emptyTreap) {
root->sz = root->left->sz + 1 + root->right->sz;
root->gcd = gcd2(gcd2(root->left->gcd, root->right->gcd), root->val);
}
}
pair<Treap*, Treap*> split(Treap* root, int 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;
} else {
ans.second = root;
pair<Treap*, Treap*>aux = split(root->left, pos);
ans.first = aux.first;
ans.second->left = aux.second;
}
recompute(ans.first);
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, 1, rand(), pos, val, val};
Treap* view = join(join(aux1.first, newTreap), aux2.second);
return view;
}
long long TreapQuery(Treap* root, long long pos1, long long pos2) {
pair<Treap*, Treap*>aux1 = split(root, pos1 - 1);
pair<Treap*, Treap*>aux2 = split(aux1.second, pos2);
long long answer = 0;
if (aux2.first != emptyTreap)
answer = aux2.first->gcd;
root = join(join(aux1.first, aux2.first), aux2.second);
return answer;
}
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 K) {
if (root == emptyTree)
root = new SegTree {emptyTreap, emptyTree, emptyTree};
root->treap = TreapUpdate(root->treap, coord(P, Q), K);
if (l == r)
return root;
int mid = (l + r) / 2;
if (P <= mid)
root->left = SegTreeUpdate(root->left, l, mid, P, Q, K);
else
root->right = SegTreeUpdate(root->right, mid + 1, r, P, Q, K);
return root;
}
long long SegTreeQuery(SegTree* root, int l, int r, int P, int Q, int U, int V) {
if (root == emptyTree)
return 0;
if (P <= l && r <= U)
return TreapQuery(root->treap, coord(P, Q), coord(U, V));
if (U < l)
return 0;
if (r < P)
return 0;
int mid = (l + r) / 2;
return gcd2(SegTreeQuery(root->left, l, mid, P, Q, U, V), SegTreeQuery(root->right, mid + 1, r, P, Q, U, V));
}
void init(int R, int C) {
srand(time(NULL));
Root = emptyTree;
N = R;
M = C;
}
void update(int P, int Q, long long K) {
Root = SegTreeUpdate(Root, 1, N, 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);
}
/*int main() {
freopen("date.in", "r", stdin);
freopen("date.out", "w", stdout);
int R, C;
scanf("%d%d", &R, &C);
init(R, C);
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int t;
scanf("%d", &t);
if (t == 1) {
int P, Q;
long long K;
scanf("%d%d", &P, &Q);
scanf("%lld", &K);
update(P, Q, K);
} else {
int P, Q, U, V;
scanf("%d%d%d%d", &P, &Q, &U, &V);
printf("%lld\n", calculate(P, Q, U, V));
}
}
return 0;
}
*/
