#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 ;
using namespace std ;
int Y[MAXN] ;
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 Treap
{
int l1, r1, l2, r2 ;
vector<int> y , L , R ;
vector<ll> mdc , val ;
int rt = 0 ;
inline void calc(int u)
{
mdc[u] = gcd2( mdc[ L[u] ] , mdc[ R[u] ] ) ;
mdc[u] = gcd2( mdc[u] , val[u] ) ;
}
int merge(int l, int r)
{
if(!l || !r) return l + r ;
int u;
if( Y[l] > Y[r] ) { R[l] = merge(R[l] , r ) ; u = l ; }
else { L[r] = merge( l , L[r] ) ; u = r ; }
calc(u) ;
return u ;
}
void splitY(int u , int &l, int &r, int x)
{
if( u == 0 ) return (void)( l = r= 0 ) ;
if( y[u] <= x )
{
splitY( R[u] , l , r , x ) ;
R[u] = l ;
l = u ;
}
else
{
splitY( L[u] , l, r , x ) ;
L[u] = r ;
r = u ;
}
calc(u) ;
}
int create(int _y, ll x)
{
y.pb(_y) ;
L.pb(0) ;
R.pb(0) ;
val.pb(x) ;
mdc.pb(x) ;
return y.size() - 1 ;
}
Treap() { create(-1,0) ; }
inline void upd(int _y , ll x )
{
splitY( rt , l1 , r1 , _y ) ;
splitY( l1, l2, r2, _y - 1 ) ;
if( r2 == 0 ) r2 = create( _y , x ) ;
val[r2] = x ;
calc(r2) ;
l1 = merge(l2, r2) ;
rt = merge(l1, r1) ;
}
ll qry( int _y1, int _y2 )
{
splitY( rt , l1 , r1 , _y2 ) ;
splitY( l1, l2, r2, _y1-1 ) ;
ll resp = mdc[r2] ;
l1 = merge(l2,r2) ;
rt = merge(l1, r1) ;
return resp ;
}
};
struct Seg
{
vector<Treap> treap ;
vector<int> e , d ;
int create()
{
e.pb(0) ;
d.pb(0) ;
treap.pb( *(new Treap) ) ;
return e.size() - 1 ;
}
inline void init()
{
e.clear() ;
d.clear() ;
treap.clear() ;
create() ;
create() ;
}
void upd(int pos, int l, int r, int x, int y, ll val )
{
if( l == r )
{
treap[pos].upd( 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 = treap[ e[pos] ].qry( y , y ) ;
ll ar = treap[ d[pos] ].qry( y , y ) ;
treap[pos].upd( 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 treap[pos].qry( 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) {
srand( time(0) ) ;
seg.init() ;
lp(i,0,MAXN) Y[i] = i ;
random_shuffle(Y, Y+MAXN) ;
}
void update(int P, int Q, long long K) { seg.upd( 1 , 0 , MAX , P , Q , K ) ;}
