#include "game.h"
#include <cstdio>
long long gcd(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
using ll = long long;
const int MU = 2.2e4+10;
const int MQ = 2.5e5+10;
const int M1 = 30 * 30 * MU;
const int M2 = 30 * MU;
int R, C, X1, X2;
ll st1[M1]; int l1[M1], r1[M1];
int st2[M2], l2[M2], r2[M2], root;
void init(int R, int C) {
::R=R, ::C=C;
}
void upd1(int& n, int l, int r, int Q, ll K)
{
if(!n) n=++X1;
if(r-l>1)
{
int m=l+(r-l)/2;
if(Q<m) upd1(l1[n], l, m, Q, K);
else upd1(r1[n], m, r, Q, K);
st1[n]=gcd(st1[l1[n]], st1[r1[n]]);
}
else
st1[n]=K;
}
void up(int& p, int a, int b, int l, int r, int Q)
{
if(!p) p=++X1;
if(r-l>1)
{
int m=l+(r-l)/2;
if(Q<m) up(l1[p], l1[a], l1[b], l, m, Q);
else up(r1[p], r1[a], r1[b], m, r, Q);
}
st1[p]=gcd(st1[a], st1[b]);
}
void upd2(int& n, int l, int r, int P, int Q, ll K)
{
if(!n) n=++X2;
if(r-l>1)
{
int m=l+(r-l)/2;
if(P<m) upd2(l2[n], l, m, P, Q, K);
else upd2(r2[n], m, r, P, Q, K);
up(st2[n], st2[l2[n]], st2[r2[n]], 0, C, Q);
}
else
upd1(st2[n], 0, C, Q, K);
}
void update(int P, int Q, long long K) {
upd2(root, 0, R, P, Q, K);
}
ll qry1(int n, int l, int r, int Q, int V)
{
if(!n) return 0;
if(Q <= l && r <= V) return st1[n];
else
{
int m=l+(r-l)/2;
ll v=0;
if(Q<m) v = gcd(v, qry1(l1[n], l, m, Q, V));
if(m<V) v = gcd(v, qry1(r1[n], m, r, Q, V));
return v;
}
}
ll qry2(int n, int l, int r, int P, int U, int Q, int V)
{
if(!n) return 0;
if(P <= l && r <= U) return qry1(st2[n], 0, C, Q, V);
else
{
int m=l+(r-l)/2;
ll v=0;
if(P<m) v = gcd(v, qry2(l2[n], l, m, P, U, Q, V));
if(m<U) v = gcd(v, qry2(r2[n], m, r, P, U, Q, V));
return v;
}
}
long long calculate(int P, int Q, int U, int V) {
return qry2(root, 0, R, P, U+1, Q, V+1);
}
