#include "game.h"
#include <bits/stdc++.h>
#define le (node<<1)
#define ri (node<<1|1)
#define mid ((l+r)>>1)
using namespace std ;
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;
}
const int N = 1e5+5 ;
int n , m ;
struct Segment_Tree {
long long tree[N<<2] ;
void build ( int node , int l , int r ) {
if ( l == r ) {
tree[node] = 0 ;
}
else {
build ( le , l , mid ) ;
build ( ri , mid+1 , r ) ;
tree[node] = gcd2 ( tree[le] , tree[ri] ) ;
}
}
void update ( int node , int l , int r , int i , long long v ) {
if ( l == r ) {
tree[node] = v ;
}
else {
if ( i <= mid ) {
update ( le , l , mid , i , v ) ;
}
else {
update ( ri , mid+1 , r , i , v ) ;
}
tree[node] = gcd2 ( tree[le] , tree[ri] ) ;
}
}
long long query ( int node , int l , int r , int x , int y ) {
if ( l > r || l > y || r < x ) {
return 0ll ;
}
if ( l >= x && r <= y ) {
return tree[node] ;
}
return gcd2 ( query ( le , l , mid , x , y ) , query ( ri , mid+1 , r , x , y ) ) ;
}
} seg[11] ;
void init(int R, int C) {
n = R ; m = C ;
for ( int i = 1 ; i <= n ; i++ ) {
seg[i].build ( 1 , 1 , m ) ;
}
}
void update(int P, int Q, long long K) {
P++ ; Q++ ;
seg[P].update ( 1 , 1 , m , Q , K ) ;
}
long long calculate(int P, int Q, int U, int V) {
long long ret = 0 ;
P++ ; Q++ ; U++ ; V++ ;
for ( int i = P ; i <= U ; i++ ) {
ret = gcd2 ( ret , seg[i].query ( 1 , 1 , m , Q , V ) ) ;
}
return ret ;
}
