#include <bits/stdc++.h>
#include "game.h"
using namespace std;
long long gcd(long long a, long long b)
{
while (b)
{
long long r = a % b;
a = b;
b = r;
}
return a;
}
struct node
{
long long val;
node *left, *right;
node() {val = 0, left = right = nullptr;}
};
struct segment_tree
{
node *root;
segment_tree *left, *right;
segment_tree() {root = new node(), left = right = nullptr;}
};
segment_tree *tr;
int r, c;
void init(int _r, int _c)
{
tr = new segment_tree();
r = _r;
c = _c;
}
void merge(node *&x)
{
x->val = 0;
if (x->left)
x->val = gcd(x->val, x->left->val);
if (x->right)
x->val = gcd(x->val, x->right->val);
}
long long small_get(node *x, int l, int r, int ll, int rr)
{
if (!x || l > rr || r < ll)
return 0;
if (l >= ll && r <= rr)
return x->val;
int mid = (l + r) / 2;
return gcd(small_get(x->left, l, mid, ll, rr), small_get(x->right, mid + 1, r, ll, rr));
}
void small_update(segment_tree *&tr, node *&x, int lx, int rx, int ly, int ry, int pos, long long val)
{
if (ly == ry)
{
if (lx == rx)
x->val = val;
else
{
x->val = 0;
if (tr->left)
x->val = gcd(x->val, small_get(tr->left->root, 0, c-1, ly, ry));
if (tr->right)
x->val = gcd(x->val, small_get(tr->right->root, 0, c-1, ly, ry));
}
return;
}
int mid = (ly + ry) / 2;
if (pos <= mid)
{
if (!x->left)
x->left = new node();
small_update(tr, x->left, lx, rx, ly, mid, pos, val);
}
else
{
if (!x->right)
x->right = new node();
small_update(tr, x->right, lx, rx, mid + 1, ry, pos, val);
}
merge(x);
}
void big_update(segment_tree *&tr, int l, int r, int x, int y, long long val)
{
if (l == r)
{
small_update(tr, tr->root, l, r, 0, c-1, y, val);
return;
}
int mid = (l + r) / 2;
if (x <= mid)
{
if (!tr->left)
tr->left = new segment_tree();
big_update(tr->left, l, mid, x, y, val);
}
else
{
if (!tr->right)
tr->right = new segment_tree();
big_update(tr->right, mid + 1, r, x, y, val);
}
small_update(tr, tr->root, l, r, 0, c-1, y, val);
}
long long big_get(segment_tree *x, int l, int r, int lx, int rx, int ly, int ry)
{
if (!x || l > rx || r < lx)
return 0;
if (l >= lx && r <= rx)
return small_get(x->root, 0, c-1, ly, ry);
int mid = (l + r) / 2;
return gcd(big_get(x->left, l, mid, lx, rx, ly, ry), big_get(x->right, mid + 1, r, lx, rx, ly, ry));
}
void update(int p, int q, long long k)
{
big_update(tr, 0, r, p, q, k);
}
long long calculate(int p, int q, int u, int v)
{
return big_get(tr, 0, r, p, u, q, v);
}
/*
int main()
{
int r1, c1, q;
cin >> r1 >> c1 >> q;
init(r1, c1);
while (q--)
{
int type;
cin >> type;
if (type == 1)
{
int p, q;
long long k;
cin >> p >> q >> k;
update(p, q, k);
}
else
{
int p, q, u, v;
cin >> p >> q >> u >> v;
cout << calculate(p, q, u, v) << endl;
}
}
}
*/
