#include <bits/stdc++.h>
#include "game.h"
typedef long long ll;
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 l, r;
ll data;
Node *Left, *Right;
Node(int _l, int _r){
l = _l;
r = _r;
data = 0;
Left = Right = nullptr;
}
ll get(int u, int v){
if (v < l || r < u || data == 0)
return 0;
if (u <= l && r <= v)
return data;
ll res = 0;
if (Left != nullptr)
res = gcd2(res, Left->get(u, v));
if (Right != nullptr)
res = gcd2(res, Right->get(u, v));
return res;
}
void update(int pos, ll val){
if (pos < l || r < pos)
return;
if (l == r){
data = val;
return;
}
int mid = (l + r) >> 1;
if (Left == nullptr)
Left = new Node(l, mid);
Left->update(pos, val);
if (Right == nullptr)
Right = new Node(mid + 1, r);
Right->update(pos, val);
data = gcd2(Left->data, Right->data);
}
};
struct Node2{
int l, r;
Node *data;
Node2 *Left, *Right;
Node2(int _l, int _r){
l = _l;
r = _r;
data = new Node(0, 1e9);
Left = Right = nullptr;
}
ll get(int x, int y, int u, int v){
if (y < l || r < x || data->data == 0)
return 0;
if (x <= l && r <= y)
return data->get(u, v);
ll res = 0;
if (Left != nullptr)
res = gcd2(res, Left->get(x, y, u, v));
if (Right != nullptr)
res = gcd2(res, Right->get(x, y, u, v));
return res;
}
void update(int x, int y, ll val){
if (x < l || r < x)
return;
if (l == r){
data->update(y, val);
return;
}
int mid = (l + r) >> 1;
if (Left == nullptr)
Left = new Node2(l, mid);
Left->update(x, y, val);
if (Right == nullptr)
Right = new Node2(mid + 1, r);
Right->update(x, y, val);
data->update(y, gcd2(Left->data->get(y, y), Right->data->get(y, y)));
}
};
Node2 *st;
void init(int r, int c) {
st = new Node2(0, 1e9);
}
void update(int p, int q, long long k) {
st->update(p, q, k);
}
long long calculate(int x, int y, int u, int v) {
return st->get(x, u, y, v);
}
