#include "game.h"
#include <bits/stdc++.h>
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define all(x) x.begin() , x.end()
#define mm(dp , val) memset (dp , val , sizeof dp)
#define mid ((r+l)>>1)
#define lx (n<<1)
#define rx ((n<<1)|1)
#define low (i&(-i))
#define lb lower_bound
#define ub upper_bound
#define no void (cout << "NO" << endl)
#define one void (cout << "-1" << endl)
#define zer void (cout << "0" << endl)
#define yes void (cout << "YES" << endl)
typedef long long ll;
using namespace std;
const int logn = 26 ;
const int N = 2e3+5;
ll dx[] = {0 , 0 , 1 , -1};
ll dy[] = {1 , -1 , 0 , 0};
long long gcd2(long long X, long long Y)
{
if (!X || !Y)
return max(X , Y) ;
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
ll n , m , a[N][N] ;
struct seg_tree
{
ll gcd[N] ;
void upd (ll n , ll l , ll r , ll i , ll v)
{
if (l == r)
{
gcd[n] = v ;
return ;
}
if (i <= mid)
upd(lx , l , mid , i , v) ;
else
upd(rx , mid+1 , r , i , v) ;
gcd[n] = gcd2(gcd[lx] , gcd[rx]) ;
}
ll qry (ll n , ll l , ll r , ll x , ll y)
{
if (l > y || r < x)
return 0 ;
if (x <= l && r<=y)
return gcd[n] ;
if (y <= mid)
return qry(lx , l , mid , x , y) ;
if (x > mid)
return qry(rx , mid+1 , r , x , y) ;
ll le = qry(lx , l , mid , x , y) ;
ll ri = qry(rx , mid+1 , r , x , y) ;
return gcd2(le , ri) ;
}
} tree[N] , tree2[N];
ll get (ll x1 , ll y1 , ll x2 , ll y2)
{
ll ret = 0 ;
if (x1 - x2 <= y1 - y2)
{
for (int i = x1 ; i<=x2 ; i++)
ret = gcd2(ret , tree[i].qry (1 , 0 , m-1 , y1 , y2));
}
else
{
for (int i = y1 ; i<= y2 ; i++)
ret = gcd2 (ret , tree2[i].qry(1 , 0 , n-1 , x1 , x2));
}
return ret ;
}
void init(int R, int C) {
n = R , m = C ;
}
void update(int P, int Q, long long K)
{
tree[P].upd(1 , 0 , m-1 , Q , K) ;
tree2[Q].upd(1 , 0 , n-1 , P , K) ;
}
long long calculate(int P, int Q, int U, int V) {
return get(P , Q , U , V) ;
}
