#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;
}
void extend()
{
if(!L)
{
L = new node2();
R = new node2();
}
}
};
struct node1
{
node2 *now;
node1 *L, *R;
node1()
{
now = new node2();
L = R = NULL;
}
void extend()
{
if(!L)
{
L = new node1();
R = new node1();
}
}
};
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;
}
void init(int R, int C) {
_R = R, _C = C;
root = new node1();
}
void update2(node2 *seg, int l, int r, int p, long long v) {
seg->extend();
if(l == r) return void(seg->v = v);
int mid = (l+r)>>1;
if(p <= mid) update2(seg->L, l, mid, p, v);
else update2(seg->R, mid+1, r, p, v);
seg->v = gcd2(seg->L->v, seg->R->v);
}
void push_seg(node2 *seg, node2 *L, node2 *R, int l, int r, int p) {
seg->extend();
L->extend();
R->extend();
if(l == r) return void(seg->v = gcd2(L->v, R->v));
int mid = (l+r)>>1;
if(p <= mid) push_seg(seg->L, L->L, R->L, l, mid, p);
else push_seg(seg->R, L->R, R->R, mid+1, r, p);
seg->v = gcd2(L->v, R->v);
}
void update1(node1 *seg, int l, int r, int p, int _p, long long v) {
seg->extend();
if(l == r) return void(update2(seg->now, 1, _C, _p, v));
int mid = (l+r)>>1;
if(p <= mid) update1(seg->L, l, mid, p, _p, v);
else update1(seg->R, mid+1, r, p, _p, v);
push_seg(seg->now, seg->L->now, seg->R->now, 1, _C, _p);
}
void update(int P, int Q, long long K) {
P++, Q++;
update1(root, 1, _R, P, Q, K);
}
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 _a, int _b) {
if(!seg || r < a || b < l) return 0;
if(a <= l && r <= b) return query2(seg->now, 1, _C, _a, _b);
int mid = (l+r)>>1;
return gcd2(query1(seg->L, l, mid, a, b, _a, _b), query1(seg->R, mid+1, r, a, b, _a, _b));
}
long long calculate(int P, int Q, int U, int V) {
P++, Q++, U++, V++;
return query1(root, 1, _R, P, U, Q, V);
}
