#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 {
long long ans;
int l, r;
Node *left, *right;
Node() {}
Node(int _l, int _r) : ans(0), l(_l), r(_r), left(NULL), right(NULL) {}
void extend() {
if (!left) {
int m = (l + r) / 2;
left = new Node(l, m);
right = new Node(m+1, r);
}
}
};
long long query(Node *p, int i, int j) {
if (i > p->r || j < p->l)
return 0;
if (i <= p->l && p->r <= j)
return p->ans;
p->extend();
return gcd2(query(p->left, i, j), query(p->right, i, j));
}
void update(Node *p, int idx, long long val) {
if (p->l == p->r) {
p->ans = val;
return;
}
p->extend();
int m = (p->l + p->r) / 2;
if (idx <= m)
update(p->left, idx, val);
else
update(p->right, idx, val);
p->ans = gcd2(p->left->ans, p->right->ans);
}
void update_y(Node *cur, Node *curL, Node *curR, int y, long long val) {
if (cur->l == cur->r) {
cur->ans = gcd2(curL->ans, curR->ans);
return;
}
cur->extend();
curL->extend();
curR->extend();
int m = (cur->l + cur->r) / 2;
if (y <= m)
update_y(cur->left, curL->left, curR->left, y, val);
else
update_y(cur->right, curL->right, curR->right, y, val);
cur->ans = gcd2(cur->left->ans, cur->right->ans);
}
struct Seg {
int n, l, r;
Node yNode;
Seg *left, *right;
Seg() {}
Seg(int _n, int _l, int _r) : n(_n), l(_l), r(_r), yNode(0, n-1), left(NULL), right(NULL) {}
void extend() {
if (!left) {
int m = (l + r) / 2;
left = new Seg(n, l, m);
right = new Seg(n, m+1, r);
}
}
} st;
long long query(Seg *p, int ix, int iy, int jx, int jy) {
if (ix > p->r || jx < p->l)
return 0;
if (ix <= p->l && p->r <= jx)
return query(&p->yNode, iy, jy);
p->extend();
return gcd2(query(p->left, ix, iy, jx, jy), query(p->right, ix, iy, jx, jy));
}
void update(Seg *p, int x, int y, long long val) {
if (p->l == p->r) {
update(&p->yNode, y, val);
return;
}
p->extend();
int m = (p->l + p->r) / 2;
if (x <= m)
update(p->left, x, y, val);
else
update(p->right, x, y, val);
update_y(&p->yNode, &p->left->yNode, &p->right->yNode, y, val);
}
void init(int R, int C) {
st = Seg(C, 0, R - 1);
}
void update(int P, int Q, long long K) {
update(&st, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return query(&st, P, Q, U, V);
}
