#include <numeric>
#include <map>
#include <algorithm>
#include <iostream>
#include "game.h"
using namespace std;
int r,c;
int const N=1e5;
map<pair<int,int>,long long>d;
struct seg1
{
long long St[4*N]={};
void update(int i,int r,int st,int en,long long val)
{
if (st==en)
{
St[i]=val;
return;
}
int mid=(st+en)/2;
if (r<=mid)
update(i*2,r,st,mid,val);
else
update(i*2+1,r,mid+1,en,val);
St[i]=gcd(St[i*2],St[i*2+1]);
}
long long get(int i,int st,int en,int l,int r)
{
if (st>=l&&en<=r)
return St[i];
if (st>r||en<l)
return 0;
int mid=(st+en)/2;
return gcd(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r));
}
};
seg1 St[10]={};
void init(int R, int C)
{
r=R;
c=C;
}
void update(int P, int Q, long long K)
{
if (r<=10)
St[P].update(1,Q,0,c-1,K);
else
d[{P,Q}]=K;;
}
long long calculate(int P, int Q, int U, int V)
{
if (r<=10)
{
long long ans=0;
for (int i=P;i<=U;i++)
{
long long z=St[i].get(1,0,c-1,Q,V);
ans=gcd(ans,z);
}
return ans;
}
long long ans=0;
for (auto i:d)
{
int x,y;
tie(x,y)=i.first;
if (x>=P&&x<=U&&y>=Q&&y<=V)
ans=gcd(ans,i.second);
}
return ans;
}
