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