#include "game.h"
#include <bits/stdc++.h>
#define le (node<<1)
#define ri (node<<1|1)
#define mid ((l+r)>>1)
#define ple (pnode<<1)
#define pri (pnode<<1|1)
const int N = 2e3+3 ;
int n , m , a[N][N] ;
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;
}
struct Segment_Tree_2D {
long long tree[N<<2][N<<2] ;
void buildy ( int pnode , int pl , int pr , int node , int l , int r ) {
if ( l == r ) {
if ( pl == pr ) {
tree[pnode][node] = a[pl][l] ;
}
else {
tree[pnode][node] = gcd2 ( tree[ple][node] , tree[pri][node] ) ;
}
return ;
}
buildy ( pnode , pl , pr , le , l , mid ) ;
buildy ( pnode , pl , pr , ri , mid+1 , r ) ;
tree[pnode][node] = gcd2 ( tree[pnode][le] , tree[pnode][ri] ) ;
}
void build ( int node , int l , int r ) {
if ( l != r ) {
build ( le , l , mid ) ;
build ( ri , mid+1 , r ) ;
}
buildy ( node , l , r , 1 , 1 , m ) ;
}
void updatey ( int pnode , int pl , int pr , int node , int l , int r , int i , long long v ) {
if ( l == r ) {
if ( pl == pr ) {
tree[pnode][node] = v ;
}
else {
tree[pnode][node] = gcd2 ( tree[ple][node] , tree[pri][node] ) ;
}
return ;
}
if ( i <= mid ) {
updatey ( pnode , pl , pr , le , l , mid , i , v ) ;
}
else {
updatey ( pnode , pl , pr , ri , mid+1 , r , i , v ) ;
}
tree[pnode][node] = gcd2 ( tree[pnode][le] , tree[pnode][ri] ) ;
}
void update ( int node , int l , int r , int i , int j , long long v ) {
if ( l != r ) {
if ( i <= mid ) {
update ( le , l , mid , i , j , v ) ;
}
else {
update ( ri , mid+1 , r , i , j , v ) ;
}
}
updatey ( node , l , r , 1 , 1 , m , j , v ) ;
}
long long queryy ( int pnode , int node , int l , int r , int x , int y ) {
if ( l > r || l > y || r < x ) {
return 0 ;
}
if ( l >= x && r <= y ) {
return tree[pnode][node] ;
}
return gcd2 ( queryy ( pnode , le , l , mid , x , y ) , queryy ( pnode , ri , mid+1 , r , x , y ) ) ;
}
long long query ( int node , int l , int r , int x , int y , int xx , int yy ) {
if ( l > r || l > y || r < x ) {
return 0 ;
}
if ( l >= x && r <= y ) {
return queryy ( node , 1 , 1 , m , xx , yy ) ;
}
return gcd2 ( query ( le , l , mid , x , y , xx , yy ) , query ( ri , mid+1 , r , x , y , xx , yy ) ) ;
}
} seg ;
void init(int R, int C) {
n = R ;
m = C ;
seg.build ( 1 , 1 , n ) ;
}
void update(int P, int Q, long long K) {
seg.update ( 1 , 1 , n , P+1 , Q+1 , K ) ;
}
long long calculate(int P, int Q, int U, int V) {
return seg.query ( 1 , 1 , n , P+1 , U+1 , Q+1 , V+1 ) ;
}
