結果

問題 No.2292 Interval Union Find
ユーザー 👑 p-adicp-adic
提出日時 2023-05-12 07:37:45
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 17,913 bytes
コンパイル時間 4,912 ms
コンパイル使用メモリ 247,052 KB
実行使用メモリ 64,384 KB
最終ジャッジ日時 2024-11-28 01:26:03
合計ジャッジ時間 38,483 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 6 WA * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize ( "O3" )
#pragma GCC optimize( "unroll-loops" )
#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr )
#define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE
#define CIN( LL , A ) LL A; cin >> A
#define ASSERT( A , MIN , MAX ) assert( ( MIN ) <= A && A <= ( MAX ) )
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ )
#define QUIT return 0
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"
template <int N>
class SqrtCalculation
{
public:
int m_val;
inline constexpr SqrtCalculation();
};
template <int N> inline constexpr SqrtCalculation<N>::SqrtCalculation() : m_val( 1 ) { int m_val2 = 1; while( ( m_val2 << 2 ) <= N ){ m_val <<= 1;
    m_val2 <<= 2; } while( m_val2 < N ){ m_val++; m_val2 = m_val * m_val; } }
#define TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION typename T , T m_T(const T&,const T&) , const T& e_T() , typename U , U m_U(const U&,const U&)
    , const U& e_U() , U o_U(const T&,const U&) , int N , int N_sqrt
// (T,m_T:T^2->T,e_T:1->T)
// (U,m_U:U^2->U,e_U:1->U)
// T(o_U:T×U->U)N
// e_UO(N)
// O(N)
// O(1)
// O(min(i_final-i_start+1,N^{1/2}))U使
// O(N^{1/2})
// O(N^{1/2})
// o_U
// o_UO(N^{1/2})
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION = SqrtCalculation<N>{}.m_val >
class LazySqrtDecomposition
{
// private:
public:
static constexpr const int N_d = ( N + N_sqrt - 1 ) / N_sqrt;
static constexpr const int N_m = N_d * N_sqrt;
U m_a[N_m];
U m_b[N_d];
U m_lazy_substitution[N_d];
bool m_suspended[N_d];
T m_lazy_action[N_d];
public:
static const T& g_e_T;
static const U& g_e_U;
inline constexpr LazySqrtDecomposition();
inline constexpr LazySqrtDecomposition( const U ( &a )[N] );
inline constexpr U Get( const int& i ) const;
inline constexpr U IntervalProd( const int& i_start , const int& i_final ) const;
inline constexpr void Set( const int& i , const U& u );
inline constexpr void IntervalSet( const int& i_start , const int& i_final , const U& u );
inline constexpr void IntervalAct( const int& i_start , const int& i_final , const T& t );
static inline constexpr U Power( const U& u , int exponent );
private:
inline constexpr U IntervalProd_Body( const int& i_min , const int& i_ulim ) const;
inline constexpr void SetProd( const int& i );
inline constexpr void SolveSuspension( const int& d , const U& u );
inline constexpr void IntervalSet_Body( const int& i_min , const int& i_ulim , const U& t );
inline constexpr void IntervalAct_Body( const int& d , T& t );
inline constexpr void IntervalAct_Body( const int& i_min , const int& i_ulim , const T& t );
};
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> const T& LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::g_e_T = e_T();
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> const U& LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::g_e_U = e_U();
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt
    >::LazySqrtDecomposition()
: m_a() , m_b() , m_lazy_substitution() , m_suspended() , m_lazy_action()
{
if( m_a[0] != g_e_U ){
for( int d = 0 ; d < N_d ; d++ ){
m_b[d] = m_lazy_substitution[d] = g_e_U;
m_suspended[d] = true;
}
}
if( m_lazy_action[0] != g_e_T ){
for( int d = 0 ; d < N_d ; d++ ){
m_lazy_action[d] = g_e_T;
}
}
}
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt
    >::LazySqrtDecomposition( const U ( &a )[N] )
: m_a() , m_b() , m_lazy_substitution() , m_suspended() , m_lazy_action()
{
int i = 0;
while( i < N ){
m_a[i] = a[i];
i++;
}
while( i < N_m ){
m_a[i] = g_e_U;
i++;
}
i = 0;
for( int d = 0 ; d < N_d ; d++ ){
U& m_bd = m_b[d] = g_e_U;
for( int j = 0 ; j < N_sqrt ; j++ ){
m_bd = m_U( m_bd , m_a[i] );
i++;
}
}
if( m_lazy_action[0] != g_e_T ){
for( int d = 0 ; d < N_d ; d++ ){
m_lazy_action[d] = g_e_T;
}
}
}
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr U LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::Get( const int&
    i ) const { const int d = i / N_sqrt; return m_suspended[d] ? m_lazy_substitution[d] : o_U( m_lazy_action[d] , m_a[i] ); }
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr U LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::IntervalProd(
    const int& i_start , const int& i_final ) const
{
const int i_min = max( i_start , 0 );
const int i_ulim = min( i_final + 1 , N );
const int d_0 = ( i_min + N_sqrt - 1 ) / N_sqrt;
const int d_1 = max( d_0 , i_ulim / N_sqrt );
const int i_0 = min( d_0 * N_sqrt , i_ulim ) ;
const int i_1 = max( i_0 , d_1 * N_sqrt );
U answer = g_e_U;
if( i_min < i_0 ){
// d_0 > 0
answer = m_suspended[d_0-1] ? Power( m_lazy_substitution[d_0-1] , i_0 - i_min ) : o_U( m_lazy_action[d_0-1] , IntervalProd_Body( i_min , i_0 ) );
}
for( int d = d_0 ; d < d_1 ; d++ ){
answer = m_U( answer , o_U( m_lazy_action[d] , m_b[d] ) );
}
if( i_1 < i_ulim ){
// d_1 < N_d
answer = m_U( answer , m_suspended[d_1] ? Power( m_lazy_substitution[d_1] , i_ulim - i_1 ) : o_U( m_lazy_action[d_1] , IntervalProd_Body( i_1 ,
        i_ulim ) ) );
}
return answer;
}
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::Set( const
    int& i , const U& u )
{
const int d = i / N_sqrt;
const int i_min = d * N_sqrt;
const int i_ulim = i_min + N_sqrt;
U& m_ai = m_a[i];
if( m_suspended[d] ){
U& m_lazy_substitution_d = m_lazy_substitution[d];
if( m_lazy_substitution_d != u ){
SolveSuspension( d , m_lazy_substitution_d );
m_ai = u;
m_b[d] = m_T( m_T( Power( m_lazy_substitution_d , i - i_min ) , u ) , Power( m_lazy_substitution_d , i_ulim - ( i + 1 ) ) );
}
} else {
T& m_lazy_action_d = m_lazy_action[d];
bool update = false;
if( m_lazy_action_d == g_e_T ){
update = m_ai != u;
} else {
update = true;
IntervalAct_Body( i_min , i_ulim , m_lazy_action_d );
m_lazy_action_d = g_e_T;
}
if( update ){
m_ai = u;
SetProd( d );
}
}
return;
}
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::IntervalSet(
    const int& i_start , const int& i_final , const U& u )
{
const int i_min = max( i_start , 0 );
const int i_ulim = min( i_final + 1 , N );
const int d_0 = ( i_min + N_sqrt - 1 ) / N_sqrt;
const int d_1 = max( d_0 , i_ulim / N_sqrt );
const int d_0_N_sqrt = d_0 * N_sqrt;
const int d_1_N_sqrt = d_1 * N_sqrt;
const int i_0 = min( d_0_N_sqrt , i_ulim );
const int i_1 = max( i_0 , d_1_N_sqrt );
if( i_min < i_0 ){
// d_0 > 0
const int d_0_minus = d_0 - 1;
const int d_0_N_sqrt_minus = d_0_N_sqrt - N_sqrt;
U& m_bd = m_b[d_0_minus];
if( m_suspended[d_0_minus] ){
U& m_lazy_substitution_d = m_lazy_substitution[d_0_minus];
SolveSuspension( d_0_minus , m_lazy_substitution_d );
IntervalSet_Body( i_min , i_0 , u );
m_bd = m_U( m_U( Power( m_lazy_substitution_d , i_min - d_0_N_sqrt_minus ) , Power( u , i_0 - i_min ) ) , Power( m_lazy_substitution_d ,
          d_0_N_sqrt - i_0 ) );
} else {
T& m_lazy_action_d = m_lazy_action[d_0_minus];
if( m_lazy_action_d != g_e_T ){
IntervalAct_Body( d_0 , m_lazy_action_d );
}
IntervalSet_Body( i_min , i_0 , u );
m_bd = m_U( m_U( IntervalProd_Body( d_0_N_sqrt_minus , i_min ) , Power( u , i_0 - i_min ) ) , IntervalProd_Body( d_0_N_sqrt , i_0 ) );
}
}
const U power = Power( u , N_sqrt );
for( int d = d_0 ; d < d_1 ; d++ ){
m_b[d] = power;
m_lazy_substitution[d] = u;
m_suspended[d] = true;
m_lazy_action[d] = g_e_T;
}
if( i_1 < i_ulim ){
// d_1 < N_d
const int d_1_N_sqrt_plus = d_1_N_sqrt + N_sqrt;
U& m_bd = m_b[d_1];
if( m_suspended[d_1] ){
U& m_lazy_substitution_d = m_lazy_substitution[d_1];
SolveSuspension( d_1 , m_lazy_substitution_d );
IntervalSet_Body( i_1 , i_ulim , u );
m_bd = m_U( m_U( Power( m_lazy_substitution_d , i_1 - d_1_N_sqrt ) , Power( u , i_ulim - i_1 ) ) , Power( m_lazy_substitution_d ,
          d_1_N_sqrt_plus - i_ulim ) );
} else {
T& m_lazy_action_d = m_lazy_action[d_1];
if( m_lazy_action_d != g_e_T ){
IntervalAct_Body( d_1 , m_lazy_action_d );
}
m_bd = m_U( m_U( IntervalProd_Body( d_1_N_sqrt , i_1 ) , Power( u , i_ulim - i_1 ) ) , IntervalProd_Body( d_1_N_sqrt_plus , i_1 ) );
}
}
return;
}
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::IntervalAct(
    const int& i_start , const int& i_final , const T& t )
{
if( t != g_e_T ){
const int i_min = max( i_start , 0 );
const int i_ulim = min( i_final + 1 , N );
const int d_0 = ( i_min + N_sqrt - 1 ) / N_sqrt;
const int d_1 = max( d_0 , i_ulim / N_sqrt );
const int d_0_N_sqrt = d_0 * N_sqrt;
const int d_1_N_sqrt = d_1 * N_sqrt;
const int i_0 = min( d_0_N_sqrt , i_ulim );
const int i_1 = max( i_0 , d_1_N_sqrt );
if( i_min < i_0 ){
// d_0 > 0
const int d_0_minus = d_0 - 1;
const int d_0_N_sqrt_minus = d_0_N_sqrt - N_sqrt;
U& m_bd = m_b[d_0_minus];
if( m_suspended[d_0_minus] ){
U& m_lazy_substitution_d = m_lazy_substitution[d_0_minus];
const U u = o_U( t , m_lazy_substitution_d );
SolveSuspension( d_0_minus , m_lazy_substitution_d );
IntervalSet_Body( i_min , i_0 , u );
m_bd = m_U( m_U( Power( m_lazy_substitution_d , i_min - d_0_N_sqrt_minus ) , Power( u , i_0 - i_min ) ) , Power( m_lazy_substitution , d_0_N_sqrt
        - i_0 ) );
} else {
T& m_lazy_action_d = m_lazy_action[d_0_minus];
if( m_lazy_action_d == g_e_T ){
IntervalAct_Body( i_min , i_0 , t );
SetProd( d_0 );
} else {
IntervalAct_Body( d_0_N_sqrt_minus , i_min , m_lazy_action_d );
IntervalAct_Body( i_min , i_0 , m_T( t , m_lazy_action_d ) );
IntervalAct_Body( i_0 , d_0_N_sqrt , m_lazy_action_d );
m_lazy_action_d = g_e_T;
SetProd( d_0 );
}
}
}
for( int d = d_0 ; d < d_1 ; d++ ){
T& m_lazy_action_d = m_lazy_action[d];
if( m_suspended[d] ){
SolveSuspension( d , o_U( m_T( t , m_lazy_action_d ) , m_lazy_substitution[d] ) );
m_lazy_action_d = g_e_T;
} else {
m_lazy_action_d = m_T( t , m_lazy_action_d );
}
}
if( i_1 < i_ulim ){
// d_1 < N_d
const int d_1_N_sqrt_plus = d_1_N_sqrt + N_sqrt;
U& m_bd = m_b[d_1];
if( m_suspended[d_1] ){
U& m_lazy_substitution_d = m_lazy_substitution[d_1];
const U u = o_U( t , m_lazy_substitution_d );
SolveSuspension( d_1 , m_lazy_substitution_d );
IntervalSet_Body( i_1 , i_ulim , u );
m_bd = m_U( m_U( Power( m_lazy_substitution_d , i_1 - d_1_N_sqrt ) , Power( u , i_ulim - i_1 ) ) , Power( m_lazy_substitution , d_1_N_sqrt_plus -
        i_ulim ) );
} else {
T& m_lazy_action_d = m_lazy_action[d_1];
if( m_lazy_action_d == g_e_T ){
IntervalAct_Body( i_1 , i_ulim , t );
SetProd( d_1 );
} else {
IntervalAct_Body( d_1_N_sqrt , i_1 , m_lazy_action_d );
IntervalAct_Body( i_1 , i_ulim , m_T( t , m_lazy_action_d ) );
IntervalAct_Body( i_ulim , d_1_N_sqrt_plus , m_lazy_action_d );
m_lazy_action_d = g_e_T;
SetProd( d_1 );
}
}
}
}
return;
}
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr U LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::Power( const U&
    u , int exponent )
{
U answer = g_e_U;
U power = u;
while( exponent > 0 ){
answer = ( exponent & 1 ) == 0 ? answer : m_U( answer , power );
power = m_U( power , power );
exponent >>= 1;
}
return answer;
}
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr U LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt
    >::IntervalProd_Body( const int& i_min , const int& i_ulim ) const
{
U answer = g_e_U;
for( int i = i_min ; i < i_ulim ; i++ ){
answer = m_U( answer , m_a[i] );
}
return answer;
}
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt>::SetProd(
    const int& d )
{
U& m_bd = m_b[d] = g_e_U;
const int i_min = d * N_sqrt;
const int i_ulim = i_min + N_sqrt;
for( int i = i_min ; i < i_ulim ; i++ ){
m_bd = m_U( m_bd , m_a[i] );
}
return;
}
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt
    >::SolveSuspension( const int& d , const U& u ) { const int i_min = d * N_sqrt; IntervalSet_Body( i_min , i_min + N_sqrt , u ); m_suspended[d] =
    false; }
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt
    >::IntervalSet_Body( const int& i_min , const int& i_ulim , const U& u )
{
for( int i = i_min ; i < i_ulim ; i++ ){
m_a[i] = u;
}
return;
}
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt
    >::IntervalAct_Body( const int& d , T& t ) { const int i_min = d * N_sqrt; IntervalAct_Body( i_min , i_min + N_sqrt , t ); t = g_e_T; }
template <TEMPLATE_ARGUMENTS_FOR_LAZY_SQRT_DECOMPOSITION> inline constexpr void LazySqrtDecomposition<T,m_T,e_T,U,m_U,e_U,o_U,N,N_sqrt
    >::IntervalAct_Body( const int& i_min , const int& i_ulim , const T& t )
{
for( int i = i_min ; i < i_ulim ; i++ ){
U& m_ai = m_a[i];
m_ai = o_U( t , m_ai );
}
return;
}
inline bool m( const bool& b0 , const bool& b1 ) { return b0 && b1; }
inline const bool& e() { static const bool b{ true }; return b; }
inline const bool& o( const bool& b0 , const bool& b1 ) { return b1; }
int main()
{
UNTIE;
CEXPR( ll , bound_N , 1000000000 );
CIN_ASSERT( N , 2 , bound_N );
CEXPR( int , bound_Q , 200000 );
CIN_ASSERT( Q , 1 , bound_Q );
map<ll,int> TheAt{};
static int type[bound_Q];
static ll L[bound_Q];
static ll R[bound_Q];
FOR( q , 0 , Q ){
CIN_ASSERT( type_q , 1 , 4 );
type[q] = type_q;
if( type_q < 3 ){
CIN_ASSERT( L_q , 1 , N );
CIN_ASSERT( R_q , L_q + 1 , N );
L[q] = L_q;
R[q] = R_q - 1;
TheAt[L_q-1];
TheAt[L_q];
TheAt[R_q-1];
TheAt[R_q];
} else if( type_q == 3 ){
CIN_ASSERT( L_q , 1 , N );
CIN_ASSERT( R_q , 1 , N );
if( L_q > R_q ){
swap( L_q , R_q );
}
L[q] = L_q;
R[q] = R_q - 1;
TheAt[L_q];
TheAt[R_q-1];
} else {
CIN_ASSERT( L_q , 1 , N );
L[q] = L_q;
TheAt[L_q-1];
TheAt[L_q];
}
}
TheAt[1];
TheAt[N];
int size = 0;
static ll TheAtInv[bound_Q * 4];
FOR_ITR( TheAt , itr , end ){
TheAtInv[size] = itr->first;
itr->second = size++;
}
CEXPR( int , bound_size , bound_Q * 4 + 2 );
constexpr int N_sqrt = SqrtCalculation<bound_size>().m_val;
// 使
static LazySqrtDecomposition<bool,m,e,bool,m,e,m,bound_size,N_sqrt> X{};
X.IntervalSet( 0 , bound_size - 1 , false );
FOR( q , 0 , Q ){
int& type_q = type[q];
if( type_q == 1 ){
X.IntervalSet( TheAt[L[q]] , TheAt[R[q]] , true );
} else if( type_q == 2 ){
X.IntervalSet( TheAt[L[q]] , TheAt[R[q]] , false );
} else if( type_q == 3 ){
COUT( X.IntervalProd( TheAt[L[q]] , TheAt[R[q]] ) ? 1 : 0 );
} else {
int i = TheAt[L[q]];
int d = i / N_sqrt;
int d_min = d;
int i_min = d_min * N_sqrt;
int d_max = d_min + 1;
int i_max = i_min + N_sqrt;
if( X.IntervalProd( i_min , i - 1 ) ){
while( d_min > 0 ? X.IntervalProd( i_min - N_sqrt , i_min - 1 ) : false ){
i_min -= N_sqrt;
d_min--;
}
if( d_min > 0 ){
while( X.Get( i_min - 1 ) ){
i_min--;
}
}
} else {
i_min = i;
while( X.Get( i_min - 1 ) ){
i_min--;
}
}
if( X.IntervalProd( i , i_max - 1 ) ){
while( d_max < X.N_d ? X.IntervalProd( i_max , i_max + N_sqrt - 1 ) : false ){
i_max += N_sqrt;
d_max++;
}
if( d_max < X.N_d ){
while( X.Get( i_max ) ){
i_max++;
}
}
} else {
i_max = i;
while( X.Get( i_max ) ){
i_max++;
}
}
COUT( ( i_max < size ? TheAtInv[i_max] : N ) - TheAtInv[i_min] + 1 );
}
}
QUIT;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0