#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int _R, _C;
struct node2
{
long long v;
node2 *L, *R;
node2()
{
v = 0;
L = R = NULL;
}
};
struct node1
{
node2 *now;
node1 *L, *R;
node1()
{
now = new node2();
L = R = NULL;
}
};
node1 *root;
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 query2(node2 *seg, int l, int r, int a, int b)
{
if(!seg || r < a || b < l) return 0;
if(a <= l && r <= b) return seg->v;
int mid = (l+r)>>1;
return gcd2(query2(seg->L, l, mid, a, b), query2(seg->R, mid+1, r, a, b));
}
long long query1(node1 *seg, int l, int r, int a, int b, int c, int d)
{
if(!seg || r < a || b < l) return 0;
if(a <= l && r <= b) return query2(seg->now, 1, _C, c, d);
int mid = (l+r)>>1;
return gcd2(query1(seg->L, l, mid, a, b, c, d), query1(seg->R, mid+1, r, a, b, c, d));
}
void update2(node2 *seg, int l, int r, int p, long long k)
{
if(l == r) return void(seg->v = k);
int mid = (l+r)>>1;
if(p <= mid)
{
if(!seg->L) seg->L = new node2();
update2(seg->L, l, mid, p, k);
}
else
{
if(!seg->R) seg->R = new node2();
update2(seg->R, mid+1, r, p, k);
}
seg->v = gcd2((seg->L) ? seg->L->v : 0,(seg->R) ? seg->R->v : 0);
}
void update1(node1 *seg, int l, int r, int p, int q, long long k)
{
if(l == r) return void(update2(seg->now, 1, _C, q, k));
int mid = (l + r)>>1;
if(p <= mid)
{
if(!seg->L) seg->L = new node1();
update1(seg->L, l, mid, p, q, k);
}
else
{
if(!seg->R) seg->R = new node1();
update1(seg->R, mid+1, r, p, q, k);
}
long long v = gcd2((seg->L) ? query2(seg->L->now, 1, _C, q, q) : 0, (seg->R) ? query2(seg->R->now, 1, _C, q, q) : 0);
update2(seg->now, 1, _C, q, v);
}
void init(int R, int C)
{
_R = R, _C = C;
root = new node1();
}
void update(int P, int Q, long long K)
{
P++, Q++;
update1(root, 1, _R, P, Q, K);
}
long long calculate(int P, int Q, int U, int V)
{
P++, Q++, U++, V++;
return query1(root, 1, _R, P, U, Q, V);
}
