#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 = 1e6+5;
ll dx[] = {0 , 0 , 1 , -1};
ll dy[] = {1 , -1 , 0 , 0};
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;
}
ll n , m ;
struct seg_tree
{
ll gcd[N] ;
void build (ll n , ll l , ll r)
{
if (l == r)
{
gcd[n] = 0 ;
return ;
}
build (lx , l , mid);
build (rx , mid+1 , r);
gcd[n] = gcd2(gcd[lx] , gcd[rx]) ;
}
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] ;
ll le = qry(lx , l , mid , x , y) ;
ll ri = qry(rx , mid+1 , r , x , y) ;
return gcd2(le , ri) ;
}
} tree[102] ;
ll get (ll x1 , ll y1 , ll x2 , ll y2)
{
ll ret = 0 ;
for (int i = x1 ; i<=x2 ; i++)
ret = gcd2(ret , tree[i].qry (1 , 0 , m-1 , y1 , y2));
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) ;
}
long long calculate(int P, int Q, int U, int V) {
return get(P , Q , U , V) ;
}
