#include "game.h"
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define mkt make_tuple
#define debug printf
#define all(x) x.begin(),x.end()
#define lp(i,a,b) for(int i = a ; i< b ; i++)
#define ss second
#define ff first
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mk make_pair
const int MAXN = 22010 ;
const int MAX = 1e9+5 ;
const int SQ = 150 ;
using namespace std ;
long long gcd2(long long X, long long Y) {
long long tmp;
if( X < Y ) swap(X,Y) ;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int m(int l, int r) { return (l+r)>>1 ; }
struct Sparse_seg
{
vector<int> e , d ;
vector<ll> mdc ;
int create()
{
e.pb(0) ;
d.pb(0) ;
mdc.pb(0) ;
return e.size() - 1 ;
}
inline void init()
{
e.clear() ;
d.clear() ;
mdc.clear() ;
create() ;
create();
}
Sparse_seg() { init() ; }
void upd(int pos, int l, int r, int idx, ll val )
{
if(l==r) return (void)( mdc[pos] = val ) ;
int aux ;
if( idx <= m(l,r) )
{
if( e[pos] == 0 ) { aux = create() ; e[pos] = aux ; }
upd( e[pos] , l , m(l,r) , idx , val ) ;
}
else
{
if( d[pos] == 0 ) { aux = create() ; d[pos] = aux ; }
upd(d[pos] , m(l,r)+1, r, idx, val) ;
}
mdc[pos] = gcd2( mdc[ e[pos] ] , mdc[ d[pos] ] ) ;
}
ll qry(int pos, int l , int r, int beg, int en)
{
if( l > en || r < beg || pos == 0 ) return 0LL ;
if( l >= beg && r <= en ) return mdc[pos];
ll al = qry( e[pos] , l , m(l,r) , beg, en ) ;
ll ar= qry(d[pos] , m(l,r) + 1 , r ,beg, en) ;
return gcd2(al, ar) ;
}
};
struct Seg
{
vector<Sparse_seg> tree ;
vector<int> e , d ;
int create()
{
e.pb(0) ;
d.pb(0) ;
tree.pb( *(new Sparse_seg) ) ;
return e.size() - 1 ;
}
inline void init()
{
e.clear() ;
d.clear() ;
tree.clear() ;
create() ;
create() ;
}
void upd(int pos, int l, int r, int x, int y, ll val )
{
if( l == r )
{
tree[pos].upd( 1 , 0 , MAX , y , val ) ;
return ;
}
int aux ;
if( x <= m(l,r) )
{
if( e[pos] == 0 ){ aux = create() ; e[pos] = aux ; }
upd( e[pos] , l , m(l,r) , x , y , val ) ;
}
else
{
if( d[pos] == 0 ) { aux = create() ; d[pos] = aux ; }
upd(d[pos] , m(l,r)+1, r, x, y, val ) ;
}
ll al = tree[ e[pos] ].qry( 1 , 0 , MAX , y , y ) ;
ll ar = tree[ d[pos] ].qry( 1 , 0 , MAX , y , y ) ;
tree[pos].upd(1 , 0 , MAX , y , gcd2( al , ar ) ) ;
}
ll qry(int pos, int l, int r, int x1, int x2, int y1, int y2)
{
if( l > x2 || r < x1 || pos == 0 ) return 0LL ;
if( l >= x1 && r <= x2 ) return tree[pos].qry( 1 , 0 , MAX , y1, y2 ) ;
ll al = qry( e[pos] , l, m(l,r) , x1, x2, y1, y2 ) ;
ll ar = qry( d[pos] , m(l,r)+1 , r , x1, x2, y1, y2 ) ;
return gcd2(al,ar) ;
}
};
int R , C , N ;
int type , p , q , u , v ;
ll k ;
Seg seg;
long long calculate(int P, int Q, int U, int V) { return seg.qry(1,0,MAX, P, U, Q, V) ; }
void init(int R, int C) { seg.init() ; }
void update(int P, int Q, long long K) { seg.upd( 1 , 0 , MAX , P , Q , K ) ;}
