// #define _GLIBCXX_DEBUG 
#include<bits/stdc++.h>
using namespace std;
using uint = unsigned int;
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) 
#define CIN( LL , A ) LL A; cin >> A 
#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define FOREQ( VAR , INITIAL , FINAL ) for( TYPE_OF( FINAL ) VAR = INITIAL ; VAR <= FINAL ; VAR ++ ) 
#define QUIT return 0 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT 
#define TMP template
#define TYP typename
#define INL inline
#define RET return
#define CST const
#define CEX constexpr
#define NEX noexcept
#define OPR operator
#define PUB public
#define PRI private
#define STT static
#define INT_REF CST int
#define CST_INT_REF CST int
#define CST_UINT_REF CST uint
// #define INT_REF int&
// #define CST_INT_REF CST int&
// #define CST_UINT_REF CST uint&
#define ACCESS( P ) ( *P ) 
TMP <TYP T>
using VLArray = list<T>;
// 以下、自分のライブラリ（https://github.com/p-adic/cpp）よりソースコードをコピーして編集している。
TMP <TYP T> class LinkedVector;
TMP <TYP T> class IToLinkedVector;
TMP <TYP T> class CSTIToLinkedVector;
TMP <TYP T> class UnionFindForest;
TMP <TYP T>
class EoLinkedVector
{
friend class LinkedVector<T>;
friend class IToLinkedVector<T>;
friend class CSTIToLinkedVector<T>;
TMP <TYP U> friend class UnionFindForest;
PRI:
T m_t;
uint m_prev_entry;
uint m_next_entry;
PRI:
INL EoLinkedVector();
INL EoLinkedVector( CST_UINT_REF prev_entry , CST_UINT_REF next_entry );
PUB:
// vectorのreserveに必要。
INL EoLinkedVector( EoLinkedVector<T>&& e );
};
TMP <TYP T> INL EoLinkedVector<T>::EoLinkedVector() : m_t() , m_prev_entry( 0 ) , m_next_entry( 0 ) {}
TMP <TYP T> INL EoLinkedVector<T>::EoLinkedVector( CST_UINT_REF prev_entry , CST_UINT_REF next_entry ) : m_t() , m_prev_entry( prev_entry ) , m_next_entry( next_entry ) {}
TMP <TYP T> INL EoLinkedVector<T>::EoLinkedVector( EoLinkedVector<T>&& e ) : m_t( move( e.m_t ) ) , m_prev_entry( move( e.m_prev_entry ) ) , m_next_entry( move( e.m_next_entry ) ) {}
TMP <TYP T> class EoLinkedVector;
TMP <TYP T> class CSTIToLinkedVector;
TMP <TYP T> class LinkedVector;
TMP <TYP T>
class IToLinkedVector
{
friend CSTIToLinkedVector<T>;
friend LinkedVector<T>;
PRI:
LinkedVector<T>* m_p;
uint m_i;
PUB:
INL IToLinkedVector( LinkedVector<T>* CST& p , CST_UINT_REF i ) NEX;
INL IToLinkedVector( CST IToLinkedVector<T>& itr ) NEX;
INL T& OPR*() CST;
INL T* OPR->() CST;
IToLinkedVector<T>& OPR=( CST IToLinkedVector<T>& itr ) NEX;
INL void OPR++( int );
INL void OPR--( int );
INL CST LinkedVector<T>& GetLinkedVector() CST NEX;
INL LinkedVector<T>& RefLinkedVector() NEX;
INL CST_UINT_REF GetIndex() CST NEX;
INL CST_UINT_REF RefIndex() NEX;
};
TMP <TYP T>
class CSTIToLinkedVector
{
friend LinkedVector<T>;
PRI:
CST LinkedVector<T>* m_p;
uint m_i;
PUB:
INL CSTIToLinkedVector( CST LinkedVector<T>* CST& p , CST_UINT_REF i ) NEX;
INL CSTIToLinkedVector( CST CSTIToLinkedVector<T>& itr ) NEX;
INL CSTIToLinkedVector( CST IToLinkedVector<T>& itr ) NEX;
INL CST T& OPR*() CST;
INL CST T* OPR->() CST;
CSTIToLinkedVector<T>& OPR=( CST CSTIToLinkedVector<T>& itr ) NEX;
CSTIToLinkedVector<T>& OPR=( CST IToLinkedVector<T>& itr ) NEX;
INL void OPR++( int );
INL void OPR--( int );
INL CST LinkedVector<T>& GetLinkedVector() CST NEX;
INL CST_UINT_REF GetIndex() CST NEX;
INL CST_UINT_REF RefIndex() NEX;
STT INL bool Equal( CST IToLinkedVector<T>& , CST IToLinkedVector<T>& ) NEX;
STT INL bool Equal( CST CSTIToLinkedVector<T>& , CST IToLinkedVector<T>& ) NEX;
STT INL bool Equal( CST IToLinkedVector<T>& , CST CSTIToLinkedVector<T>& ) NEX;
STT INL bool Equal( CST CSTIToLinkedVector<T>& , CST CSTIToLinkedVector<T>& ) NEX;
};
TMP <TYP T> INL bool OPR==( CST IToLinkedVector<T>& , CST IToLinkedVector<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST IToLinkedVector<T>& , CST IToLinkedVector<T>& ) NEX;
TMP <TYP T> INL bool OPR==( CST CSTIToLinkedVector<T>& , CST IToLinkedVector<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST CSTIToLinkedVector<T>& , CST IToLinkedVector<T>& ) NEX;
TMP <TYP T> INL bool OPR==( CST IToLinkedVector<T>& , CST CSTIToLinkedVector<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST IToLinkedVector<T>& , CST CSTIToLinkedVector<T>& ) NEX;
TMP <TYP T> INL bool OPR==( CST CSTIToLinkedVector<T>& , CST CSTIToLinkedVector<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST CSTIToLinkedVector<T>& , CST CSTIToLinkedVector<T>& ) NEX;
// IToLinkedVector
TMP <TYP T> INL IToLinkedVector<T>::IToLinkedVector( LinkedVector<T>* CST& p , CST_UINT_REF i ) NEX : m_p( p ) , m_i( i ) {}
TMP <TYP T> INL IToLinkedVector<T>::IToLinkedVector( CST IToLinkedVector<T>& itr ) NEX : m_p( itr.m_p ) , m_i( itr.m_i ) {}
TMP <TYP T> INL T& IToLinkedVector<T>::OPR*() CST { RET ( *m_p )[m_i]; }
TMP <TYP T> INL T* IToLinkedVector<T>::OPR->() CST { RET &( ( *m_p )[m_i] ); }
TMP <TYP T> INL IToLinkedVector<T>& IToLinkedVector<T>::OPR=( CST IToLinkedVector<T>& itr ) NEX { m_p = itr.m_p; m_i = itr.m_i; RET *this; }
TMP <TYP T> INL void IToLinkedVector<T>::OPR++( int ) { m_i = m_p->m_entry[m_i].m_next_entry; }
TMP <TYP T> INL void IToLinkedVector<T>::OPR--( int ) { m_i = m_p->m_entry[m_i].m_prev_entry; }
TMP <TYP T> INL CST LinkedVector<T>& IToLinkedVector<T>::GetLinkedVector() CST NEX { RET *m_p; }
TMP <TYP T> INL LinkedVector<T>& IToLinkedVector<T>::RefLinkedVector() NEX { RET *m_p; }
TMP <TYP T> INL CST_UINT_REF IToLinkedVector<T>::GetIndex() CST NEX { RET m_i; }
TMP <TYP T> INL CST_UINT_REF IToLinkedVector<T>::RefIndex() NEX { RET m_i; }
// CSTIToLinkedVector
TMP <TYP T> INL CSTIToLinkedVector<T>::CSTIToLinkedVector( CST LinkedVector<T>* CST& p , CST_UINT_REF i ) NEX : m_p( p ) , m_i( i ) {}
TMP <TYP T> INL CSTIToLinkedVector<T>::CSTIToLinkedVector( CST CSTIToLinkedVector<T>& itr ) NEX : m_p( itr.m_p ) , m_i( itr.m_i ) {}
TMP <TYP T> INL CSTIToLinkedVector<T>::CSTIToLinkedVector( CST IToLinkedVector<T>& itr ) NEX : m_p( itr.m_p ) , m_i( itr.m_i ) {}
TMP <TYP T> INL CST T& CSTIToLinkedVector<T>::OPR*() CST { RET ( *m_p )[m_i]; }
TMP <TYP T> INL CST T* CSTIToLinkedVector<T>::OPR->() CST { RET &( ( *m_p )[m_i] ); }
TMP <TYP T>
CSTIToLinkedVector<T>& CSTIToLinkedVector<T>::OPR=( CST CSTIToLinkedVector<T>& itr ) NEX { m_p = itr.m_p; m_i = itr.m_i; RET *this; }
TMP <TYP T>
CSTIToLinkedVector<T>& CSTIToLinkedVector<T>::OPR=( CST IToLinkedVector<T>& itr ) NEX { m_p = itr.m_p; m_i = itr.m_i; RET *this; }
TMP <TYP T> INL void CSTIToLinkedVector<T>::OPR++( int ) { m_i = m_p->m_entry[m_i].m_next_entry; }
TMP <TYP T> INL void CSTIToLinkedVector<T>::OPR--( int ) { m_i = m_p->m_entry[m_i].m_prev_entry; }
TMP <TYP T> INL CST LinkedVector<T>& CSTIToLinkedVector<T>::GetLinkedVector() CST NEX { RET *m_p; }
TMP <TYP T> INL CST_UINT_REF CSTIToLinkedVector<T>::GetIndex() CST NEX { RET m_i; }
TMP <TYP T> INL CST_UINT_REF CSTIToLinkedVector<T>::RefIndex() NEX { RET m_i; }
TMP <TYP T> INL bool CSTIToLinkedVector<T>::Equal( CST IToLinkedVector<T>& itr0 , CST IToLinkedVector<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p && itr0.m_i == itr1.m_i; }
TMP <TYP T> INL bool CSTIToLinkedVector<T>::Equal( CST CSTIToLinkedVector<T>& itr0 , CST IToLinkedVector<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p && itr0.m_i == itr1.m_i; }
TMP <TYP T> INL bool CSTIToLinkedVector<T>::Equal( CST IToLinkedVector<T>& itr0 , CST CSTIToLinkedVector<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p && itr0.m_i == itr1.m_i; }
TMP <TYP T> INL bool CSTIToLinkedVector<T>::Equal( CST CSTIToLinkedVector<T>& itr0 , CST CSTIToLinkedVector<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p && itr0.m_i == itr1.m_i; }
TMP <TYP T> INL bool OPR==( CST IToLinkedVector<T>& itr0 , CST IToLinkedVector<T>& itr1 ) NEX { RET CSTIToLinkedVector<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST IToLinkedVector<T>& itr0 , CST IToLinkedVector<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> INL bool OPR==( CST CSTIToLinkedVector<T>& itr0 , CST IToLinkedVector<T>& itr1 ) NEX { RET CSTIToLinkedVector<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST CSTIToLinkedVector<T>& itr0 , CST IToLinkedVector<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> INL bool OPR==( CST IToLinkedVector<T>& itr0 , CST CSTIToLinkedVector<T>& itr1 ) NEX { RET CSTIToLinkedVector<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST IToLinkedVector<T>& itr0 , CST CSTIToLinkedVector<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> INL bool OPR==( CST CSTIToLinkedVector<T>& itr0 , CST CSTIToLinkedVector<T>& itr1 ) NEX { RET CSTIToLinkedVector<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST CSTIToLinkedVector<T>& itr0 , CST CSTIToLinkedVector<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> class IToLinkedVector;
TMP <TYP T> class CSTIToLinkedVector;
TMP <TYP T>
class LinkedVector
{
friend IToLinkedVector<T>;
friend CSTIToLinkedVector<T>;
protected:
vector<EoLinkedVector<T> > m_entry;
uint m_front_linked_entry;
uint m_back_linked_entry;
uint m_size_of_vector;
uint m_size_of_link;
PUB:
INL LinkedVector();
// 要素やそのメンバへのポインタをメンバに持ちうるクラスに対しては
// vectorのcapacityを超える際のコピーでポインタの参照先が無効になってしまうので
// 予め最大要素数を設定する。
INL LinkedVector( CST_UINT_REF max_size );
// vector上でi番目の要素を返す。
INL CST T& OPR[]( CST_UINT_REF i ) CST;
INL T& OPR[]( CST_UINT_REF i );
// link上でi番目の要素の座標を返す。
uint GetLinkedEntry( CST_UINT_REF i ) CST;
INL CST_UINT_REF GetFrontLinkedEntryIndex() CST NEX;
INL CST_UINT_REF GetBackLinkedEntryIndex() CST NEX;
INL CST_UINT_REF GetSizeOfVector() CST NEX;
INL CST_UINT_REF GetSizeOfLink() CST NEX;
INL bool EmptyVector() CST NEX;
INL bool EmptyLink() CST NEX;
INL void push_back();
TMP <TYP U> void push_back( CST U& u );
TMP <TYP U , TYP... ARGS> INL void push_back( CST U& u , CST ARGS&... args );
INL void SetPreviousLink( CST_UINT_REF i , CST_UINT_REF j );
INL void SetNexttLink( CST_UINT_REF i , CST_UINT_REF j );
INL CST_UINT_REF GetPreviousLinkIndex( CST_UINT_REF i ) CST;
INL CST_UINT_REF GetNexttLinkIndex( CST_UINT_REF i ) CST;
// vector上でi番目の要素がlink上にある場合のみサポート
CST_UINT_REF DeLink( CST_UINT_REF i );
// vector上でi番目の要素がlink上にない場合のみサポート
void ReLink( CST_UINT_REF i );
using iterator = IToLinkedVector<T>;
using CST_iterator = CSTIToLinkedVector<T>;
// *thisがCSTである場合に確実にCST_iterator返しをするために、iterator返しは非CSTにする必要がある。
INL iterator GetIterator( CST_UINT_REF i ) NEX;
INL CST_iterator GetIterator( CST_UINT_REF i ) CST NEX;
INL iterator begin() NEX;
INL CST_iterator begin() CST NEX;
INL iterator end() NEX;
INL CST_iterator end() CST NEX;
// itrの指す要素がlink上にある場合のみサポート
iterator erase( iterator& itr );
protected:
INL EoLinkedVector<T>& push_back_Body_0();
INL void push_back_Body_1( EoLinkedVector<T>& e );
};
TMP <TYP T> INL LinkedVector<T>::LinkedVector() : m_entry( 1 ) , m_front_linked_entry( 0 ) , m_back_linked_entry( 0 ) , m_size_of_vector( 0 ) , m_size_of_link( 0 ) {}
TMP <TYP T>
LinkedVector<T>::LinkedVector( CST_UINT_REF max_size ) : m_entry() , m_front_linked_entry( 0 ) , m_back_linked_entry( 0 ) , m_size_of_vector( 0 ) , m_size_of_link( 0 )
{
m_entry.shrink_to_fit();
CST uint capacity = m_entry.capacity();
m_entry.reserve( max_size + 1 );
// 一旦メモリの再確保を生じさせる。
for( uint i = 0 ; i <= capacity ; i++ ){
m_entry.push_back( EoLinkedVector<T>() );
}
for( uint i = 0 ; i < capacity ; i++ ){
m_entry.pop_back();
}
}
TMP <TYP T> INL CST T& LinkedVector<T>::OPR[]( CST_UINT_REF i ) CST { RET m_entry[i].m_t; }
TMP <TYP T> INL T& LinkedVector<T>::OPR[]( CST_UINT_REF i ) { RET m_entry[i].m_t; }
TMP <TYP T>
uint LinkedVector<T>::GetLinkedEntry( CST_UINT_REF i ) CST
{
uint linked_entry = m_front_linked_entry;
for( uint j = 0 ; j < i ; j++ ){
linked_entry = m_entry[linked_entry].m_next_entry;
}
RET linked_entry;
}
TMP <TYP T> INL CST_UINT_REF LinkedVector<T>::GetFrontLinkedEntryIndex() CST NEX { RET m_front_linked_entry; }
TMP <TYP T> INL CST_UINT_REF LinkedVector<T>::GetBackLinkedEntryIndex() CST NEX { RET m_back_linked_entry; }
TMP <TYP T> INL CST_UINT_REF LinkedVector<T>::GetSizeOfVector() CST NEX { RET m_size_of_vector; }
TMP <TYP T> INL CST_UINT_REF LinkedVector<T>::GetSizeOfLink() CST NEX { RET m_size_of_link; }
TMP <TYP T> INL bool LinkedVector<T>::EmptyVector() CST NEX { RET m_size_of_vector == 0; }
TMP <TYP T> INL bool LinkedVector<T>::EmptyLink() CST NEX { RET m_size_of_link == 0; }
TMP <TYP T> INL void LinkedVector<T>::push_back() {}
TMP <TYP T> TMP <TYP U>
void LinkedVector<T>::push_back( CST U& u )
{
EoLinkedVector<T>& e = push_back_Body_0();
e.m_t = u;
push_back_Body_1( e );
RET;
}
TMP <TYP T> TMP <TYP U , TYP... ARGS> INL void LinkedVector<T>::push_back( CST U& u , CST ARGS&... args ) { push_back( u ); push_back( args... ); }
TMP <TYP T> INL EoLinkedVector<T>& LinkedVector<T>::push_back_Body_0() { m_entry.push_back( EoLinkedVector<T>( m_size_of_vector , m_front_linked_entry ) ); RET m_entry[m_size_of_vector]; }
TMP <TYP T> INL void LinkedVector<T>::push_back_Body_1( EoLinkedVector<T>& e ) { e.m_next_entry = m_size_of_vector + 1; m_entry[m_front_linked_entry].m_prev_entry = m_size_of_vector + 1; m_back_linked_entry = m_size_of_vector; m_size_of_vector++; m_size_of_link++; }
TMP <TYP T> INL void LinkedVector<T>::SetPreviousLink( CST_UINT_REF i , CST_UINT_REF j ) { m_entry[i].m_prev_entry = j; }
TMP <TYP T> INL void LinkedVector<T>::SetNexttLink( CST_UINT_REF i , CST_UINT_REF j ) { m_entry[i].m_next_entry = j; }
TMP <TYP T> INL CST_UINT_REF LinkedVector<T>::GetPreviousLinkIndex( CST_UINT_REF i ) CST { RET m_entry[i].m_prev_entry; }
TMP <TYP T> INL CST_UINT_REF LinkedVector<T>::GetNexttLinkIndex( CST_UINT_REF i ) CST { RET m_entry[i].m_next_entry; }
TMP <TYP T>
CST_UINT_REF LinkedVector<T>::DeLink( CST_UINT_REF i )
{
CST EoLinkedVector<T>& e = m_entry[i];
m_entry[e.m_prev_entry].m_next_entry = e.m_next_entry;
m_entry[e.m_next_entry].m_prev_entry = e.m_prev_entry;
if( m_front_linked_entry == i ){
m_front_linked_entry = e.m_next_entry;
}
if( m_back_linked_entry == i ){
m_back_linked_entry = e.m_prev_entry;
}
m_size_of_link--;
RET e.m_next_entry;
}
TMP <TYP T>
void LinkedVector<T>::ReLink( CST_UINT_REF i )
{
EoLinkedVector<T>& current_entry = m_entry[i];
if( m_size_of_link == 0 ){
EoLinkedVector<T>& end_entry = m_entry[m_size_of_vector];
end_entry.m_prev_entry = end_entry.m_next_entry = i;
current_entry.m_prev_entry = current_entry.m_next_entry = m_size_of_vector;
m_front_linked_entry = m_back_linked_entry = i;
} else {
uint prev;
if( m_front_linked_entry > i ){
m_front_linked_entry = i;
prev = m_size_of_vector;
} else {
prev = m_front_linked_entry;
}
if( m_back_linked_entry < i ){
m_back_linked_entry = i;
}
prev = m_entry[prev].m_next_entry;
while( prev < i ){
prev = m_entry[prev].m_next_entry;
}
CST uint next = prev;
EoLinkedVector<T>& next_entry = m_entry[next];
prev = next_entry.m_prev_entry;
EoLinkedVector<T>& prev_entry = m_entry[prev];
prev_entry.m_next_entry = i;
current_entry.m_prev_entry = prev;
current_entry.m_next_entry = next;
next_entry.m_prev_entry = i;
}
m_size_of_link++;
RET;
}
TMP <TYP T> INL TYP LinkedVector<T>::iterator LinkedVector<T>::GetIterator( CST_UINT_REF i ) NEX { RET TYP LinkedVector<T>::iterator( this , i ); }
TMP <TYP T> INL TYP LinkedVector<T>::CST_iterator LinkedVector<T>::GetIterator( CST_UINT_REF i ) CST NEX { RET TYP LinkedVector<T>::CST_iterator( this , i ); }
TMP <TYP T> INL TYP LinkedVector<T>::iterator LinkedVector<T>::begin() NEX { RET TYP LinkedVector<T>::iterator( this , m_front_linked_entry ); }
TMP <TYP T> INL TYP LinkedVector<T>::CST_iterator LinkedVector<T>::begin() CST NEX { RET TYP LinkedVector<T>::CST_iterator( this , m_front_linked_entry ); }
TMP <TYP T> INL TYP LinkedVector<T>::iterator LinkedVector<T>::end() NEX { RET TYP LinkedVector<T>::iterator( this , m_size_of_vector ); }
TMP <TYP T> INL TYP LinkedVector<T>::CST_iterator LinkedVector<T>::end() CST NEX { RET TYP LinkedVector<T>::CST_iterator( this , m_size_of_vector ); }
TMP <TYP T> TYP LinkedVector<T>::iterator LinkedVector<T>::erase( TYP LinkedVector<T>::iterator& itr ) { RET TYP LinkedVector<T>::iterator( this , DeLink( itr.m_i ) ); }
TMP <TYP T> class IToVLTree;
TMP <TYP T> class CSTIToVLTree;
TMP <TYP T> class VLSubTree;
TMP <TYP T> class EoUnionFindForest;
TMP <TYP T>
class EoVLTree
{
friend IToVLTree<T>;
friend CSTIToVLTree<T>;
friend VLSubTree<T>;
friend EoUnionFindForest<T>;
PRI:
T m_t;
EoVLTree<T>* m_left_branch;
EoVLTree<T>* m_right_branch;
EoVLTree<T>* m_leftmost_node;
EoVLTree<T>* m_rightmost_node;
PRI:
INL EoVLTree();
TMP <TYP Arg> INL EoVLTree( CST Arg& );
TMP <TYP Arg> INL EoVLTree( CST Arg& , EoVLTree<T>* CST& , EoVLTree<T>* CST& );
INL EoVLTree( CST EoVLTree<T>& );
EoVLTree<T>& OPR=( CST EoVLTree<T>& );
};
TMP <TYP T> INL EoVLTree<T>::EoVLTree() : m_t() , m_left_branch( this ) , m_right_branch( this ) , m_leftmost_node( this ) , m_rightmost_node( this ) {}
TMP <TYP T> TMP <TYP Arg> INL EoVLTree<T>::EoVLTree( CST Arg& t ) : EoVLTree( t , this , this ) {}
TMP <TYP T> TMP <TYP Arg> INL EoVLTree<T>::EoVLTree( CST Arg& t , EoVLTree<T>* CST& left_branch , EoVLTree<T>* CST& right_branch ) : m_t( t ) , m_left_branch( left_branch ) , m_right_branch( right_branch ) , m_leftmost_node( this ) , m_rightmost_node( this ) {}
TMP <TYP T> INL EoVLTree<T>::EoVLTree( CST EoVLTree<T>& e ) : m_t( e.m_t ) , m_left_branch( e.m_left_branch == &e ? this : e.m_left_branch ) , m_right_branch( e.m_right_branch == &e ? this : e.m_right_branch ) , m_leftmost_node( this ) , m_rightmost_node( this ) { if( e.m_leftmost_node != &e ){ m_leftmost_node = e.m_leftmost_node; m_rightmost_node = e.m_rightmost_node; } }
TMP <TYP T> EoVLTree<T>& EoVLTree<T>::OPR=( CST EoVLTree<T>& e )
{
m_t = e.m_t;
m_left_branch = ( e.m_left_branch == &e ? this : e.m_left_branch );
m_right_branch = ( e.m_right_branch == &e ? this : e.m_right_branch );
if( e.m_leftmost_node == &e ){
m_leftmost_node = m_rightmost_node = this;
} else {
m_leftmost_node = e.m_leftmost_node;
m_rightmost_node = e.m_rightmost_node;
}
RET *this;
}
TMP <TYP T> class EoVLTree;
TMP <TYP T> class CSTIToVLTree;
TMP <TYP T> class VLSubTree;
TMP <TYP T> class EoVLArray;
TMP <TYP T>
class IToVLTree
{
friend CSTIToVLTree<T>;
friend VLSubTree<T>;
friend EoVLArray<IToVLTree<T> >;
PRI:
EoVLTree<T>* m_p;
PRI:
// SqIteratorOVLTree経由でのみ呼び出し可能。
INL IToVLTree() NEX;
PUB:
INL IToVLTree( EoVLTree<T>* CST& ) NEX;
INL IToVLTree( CST IToVLTree<T>& ) NEX;
INL T& OPR*() CST;
INL T* OPR->() CST;
IToVLTree<T>& OPR=( CST IToVLTree<T>& ) NEX;
// 通常と異なり自身への参照を渡す。
IToVLTree<T>& OPR++( int ) NEX;
IToVLTree<T>& OPR--( int ) NEX;
// 引数が0の時は何もしない。正の時はm_leftmost_nodeに進んでインクリメント、負の時はm_rightmost_nodeに進んでディクリメント。
IToVLTree<T>& OPR[]( CST_INT_REF );
IToVLTree<T>& Shift() NEX;
TMP <TYP... Args> IToVLTree<T>& Shift( CST_INT_REF , CST Args&... );
INL bool IsLeaf() CST NEX;
INL bool IsLeftMost() CST NEX;
INL bool IsRightMost() CST NEX;
INL bool IsValid() CST NEX;
};
TMP <TYP T>
class CSTIToVLTree
{
friend VLSubTree<T>;
friend EoVLArray<CSTIToVLTree<T> >;
PRI:
CST EoVLTree<T>* m_p;
PRI:
// SqCSTIteratorOVLTree経由でのみ呼び出し可能。
INL CSTIToVLTree() NEX;
PUB:
INL CSTIToVLTree( CST EoVLTree<T>* CST& ) NEX;
INL CSTIToVLTree( CST CSTIToVLTree<T>& ) NEX;
INL CSTIToVLTree( CST IToVLTree<T>& ) NEX;
INL CST T& OPR*() CST;
INL CST T* OPR->() CST;
CSTIToVLTree<T>& OPR=( CST CSTIToVLTree<T>& ) NEX;
CSTIToVLTree<T>& OPR=( CST IToVLTree<T>& ) NEX;
// 通常と異なり自身への参照を渡す。
CSTIToVLTree<T>& OPR++( int ) NEX;
CSTIToVLTree<T>& OPR--( int ) NEX;
// 引数が0の時は何もしない。正の時はm_leftmost_nodeに進んでインクリメント、負の時はm_rightmost_nodeに進んでディクリメント。
CSTIToVLTree<T>& OPR[]( CST_INT_REF );
CSTIToVLTree<T>& Shift() NEX;
TMP <TYP... Args> CSTIToVLTree<T>& Shift( CST_INT_REF , CST Args&... );
INL bool IsLeaf() CST NEX;
INL bool IsLeftMost() CST NEX;
INL bool IsRightMost() CST NEX;
INL bool IsValid() CST NEX;
STT INL bool Equal( CST IToVLTree<T>& , CST IToVLTree<T>& ) NEX;
STT INL bool Equal( CST CSTIToVLTree<T>& , CST IToVLTree<T>& ) NEX;
STT INL bool Equal( CST IToVLTree<T>& , CST CSTIToVLTree<T>& ) NEX;
STT INL bool Equal( CST CSTIToVLTree<T>& , CST CSTIToVLTree<T>& ) NEX;
};
TMP <TYP T> INL bool OPR==( CST IToVLTree<T>& , CST IToVLTree<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST IToVLTree<T>& , CST IToVLTree<T>& ) NEX;
TMP <TYP T> INL bool OPR==( CST CSTIToVLTree<T>& , CST IToVLTree<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST CSTIToVLTree<T>& , CST IToVLTree<T>& ) NEX;
TMP <TYP T> INL bool OPR==( CST IToVLTree<T>& , CST CSTIToVLTree<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST IToVLTree<T>& , CST CSTIToVLTree<T>& ) NEX;
TMP <TYP T> INL bool OPR==( CST CSTIToVLTree<T>& , CST CSTIToVLTree<T>& ) NEX;
TMP <TYP T> INL bool OPR!=( CST CSTIToVLTree<T>& , CST CSTIToVLTree<T>& ) NEX;
// IToVLTree
TMP <TYP T> INL IToVLTree<T>::IToVLTree() NEX : m_p( nullptr ) {}
TMP <TYP T> INL IToVLTree<T>::IToVLTree( EoVLTree<T>* CST& p ) NEX : m_p( p ) {}
TMP <TYP T> INL IToVLTree<T>::IToVLTree( CST IToVLTree<T>& itr ) NEX : m_p( itr.m_p ) {}
TMP <TYP T> INL T& IToVLTree<T>::OPR*() CST { RET m_p->m_t; }
TMP <TYP T> INL T* IToVLTree<T>::OPR->() CST { RET &( *( *this ) ); }
TMP <TYP T>
IToVLTree<T>& IToVLTree<T>::OPR=( CST IToVLTree<T>& itr ) NEX
{
m_p = itr.m_p;
RET *this;
}
TMP <TYP T>
IToVLTree<T>& IToVLTree<T>::OPR++( int ) NEX
{
if( m_p == nullptr ){
RET *this;
}
if( m_p == m_p->m_right_branch ){
m_p = nullptr;
} else {
m_p = m_p->m_right_branch;
}
RET *this;
}
TMP <TYP T>
IToVLTree<T>& IToVLTree<T>::OPR--( int ) NEX
{
if( m_p == nullptr ){
RET *this;
}
if( m_p == m_p->m_left_branch ){
m_p = nullptr;
} else {
m_p = m_p->m_left_branch;
}
RET *this;
}
TMP <TYP T>
IToVLTree<T>& IToVLTree<T>::OPR[]( CST_INT_REF n )
{
if( n > 0 ){
m_p = m_p->m_leftmost_node;
for( int i = 1 ; i < n ; i++ ){
m_p = m_p->m_right_branch;
}
} else {
if( n < 0 ){
m_p = m_p->m_rightmost_node;
for( int i = -1 ; n < i ; i-- ){
m_p = m_p->m_left_branch;
}
}
}
RET *this;
}
TMP <TYP T> IToVLTree<T>& IToVLTree<T>::Shift() NEX { RET *this; }
TMP <TYP T> TMP <TYP... Args> IToVLTree<T>& IToVLTree<T>::Shift( CST_INT_REF n , CST Args&... args ) { OPR[]( n ); RET Shift( args... ); }
TMP <TYP T> INL bool IToVLTree<T>::IsLeaf() CST NEX { RET ( m_p == nullptr ) ? false : ( m_p == m_p->m_leftmost_node ); }
TMP <TYP T> INL bool IToVLTree<T>::IsLeftMost() CST NEX { RET ( m_p == nullptr ) ? false : ( m_p == m_p->m_left_branch ); }
TMP <TYP T> INL bool IToVLTree<T>::IsRightMost() CST NEX { RET ( m_p == nullptr ) ? false : ( m_p == m_p->m_right_branch ); }
TMP <TYP T> INL bool IToVLTree<T>::IsValid() CST NEX { RET m_p != nullptr; }
// CSTIToVLTree
TMP <TYP T> INL CSTIToVLTree<T>::CSTIToVLTree() NEX : m_p( nullptr ) {}
TMP <TYP T> INL CSTIToVLTree<T>::CSTIToVLTree( CST EoVLTree<T>* CST& p ) NEX : m_p( p ) {}
TMP <TYP T> INL CSTIToVLTree<T>::CSTIToVLTree( CST CSTIToVLTree<T>& itr ) NEX : m_p( itr.m_p ) {}
TMP <TYP T> INL CSTIToVLTree<T>::CSTIToVLTree( CST IToVLTree<T>& itr ) NEX : m_p( itr.m_p ) {}
TMP <TYP T> INL CST T& CSTIToVLTree<T>::OPR*() CST { RET m_p->m_t; };
TMP <TYP T> INL CST T* CSTIToVLTree<T>::OPR->() CST { RET &( *( *this ) ); }
TMP <TYP T>
CSTIToVLTree<T>& CSTIToVLTree<T>::OPR=( CST CSTIToVLTree<T>& itr ) NEX
{
m_p = itr.m_p;
RET *this;
}
TMP <TYP T>
CSTIToVLTree<T>& CSTIToVLTree<T>::OPR=( CST IToVLTree<T>& itr ) NEX
{
m_p = itr.m_p;
RET *this;
}
TMP <TYP T>
CSTIToVLTree<T>& CSTIToVLTree<T>::OPR++( int ) NEX
{
if( m_p == nullptr ){
RET *this;
}
if( m_p == m_p->m_right_branch ){
m_p = nullptr;
} else {
m_p = m_p->m_right_branch;
}
RET *this;
}
TMP <TYP T>
CSTIToVLTree<T>& CSTIToVLTree<T>::OPR--( int ) NEX
{
if( m_p == nullptr ){
RET *this;
}
if( m_p == m_p->m_left_branch ){
m_p = nullptr;
} else {
m_p = m_p->m_left_branch;
}
RET *this;
}
TMP <TYP T>
CSTIToVLTree<T>& CSTIToVLTree<T>::OPR[]( CST_INT_REF n )
{
if( n > 0 ){
m_p = m_p->m_leftmost_node;
for( int i = 1 ; i < n ; i++ ){
m_p = m_p->m_right_branch;
}
}
if( n < 0 ){
m_p = m_p->m_rightmost_node;
for( int i = -1 ; n < i ; i-- ){
m_p = m_p->m_left_branch;
}
}
RET *this;
}
TMP <TYP T> CSTIToVLTree<T>& CSTIToVLTree<T>::Shift() NEX { RET *this; }
TMP <TYP T> TMP <TYP... Args> CSTIToVLTree<T>& CSTIToVLTree<T>::Shift( CST_INT_REF n , CST Args&... args ) { OPR[]( n ); RET Shift( args... ); }
TMP <TYP T> INL bool CSTIToVLTree<T>::IsLeaf() CST NEX { RET ( m_p == nullptr ) ? false : ( m_p == m_p->m_leftmost_mode ); }
TMP <TYP T> INL bool CSTIToVLTree<T>::IsLeftMost() CST NEX { RET ( m_p == nullptr ) ? false : ( m_p == m_p->m_left_branch ); }
TMP <TYP T> INL bool CSTIToVLTree<T>::IsRightMost() CST NEX { RET ( m_p == nullptr ) ? false : ( m_p == m_p->m_right_branch ); }
TMP <TYP T> INL bool CSTIToVLTree<T>::IsValid() CST NEX { RET m_p != nullptr; }
TMP <TYP T> INL bool CSTIToVLTree<T>::Equal( CST IToVLTree<T>& itr0 , CST IToVLTree<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p; }
TMP <TYP T> INL bool CSTIToVLTree<T>::Equal( CST CSTIToVLTree<T>& itr0 , CST IToVLTree<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p; }
TMP <TYP T> INL bool CSTIToVLTree<T>::Equal( CST IToVLTree<T>& itr0 , CST CSTIToVLTree<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p; }
TMP <TYP T> INL bool CSTIToVLTree<T>::Equal( CST CSTIToVLTree<T>& itr0 , CST CSTIToVLTree<T>& itr1 ) NEX { RET itr0.m_p == itr1.m_p; }
TMP <TYP T> INL bool OPR==( CST IToVLTree<T>& itr0 , CST IToVLTree<T>& itr1 ) NEX { RET CSTIToVLTree<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST IToVLTree<T>& itr0 , CST IToVLTree<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> INL bool OPR==( CST CSTIToVLTree<T>& itr0 , CST IToVLTree<T>& itr1 ) NEX { RET CSTIToVLTree<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST CSTIToVLTree<T>& itr0 , CST IToVLTree<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> INL bool OPR==( CST IToVLTree<T>& itr0 , CST CSTIToVLTree<T>& itr1 ) NEX { RET CSTIToVLTree<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST IToVLTree<T>& itr0 , CST CSTIToVLTree<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> INL bool OPR==( CST CSTIToVLTree<T>& itr0 , CST CSTIToVLTree<T>& itr1 ) NEX { RET CSTIToVLTree<T>::Equal( itr0 , itr1 ); }
TMP <TYP T> INL bool OPR!=( CST CSTIToVLTree<T>& itr0 , CST CSTIToVLTree<T>& itr1 ) NEX { RET !( itr0 == itr1 );}
TMP <TYP T> class VLTree;
TMP <TYP T> class EoUnionFindForest;
TMP <TYP T>
class VLSubTree
{
friend VLTree<T>;
friend EoUnionFindForest<T>;
friend UnionFindForest<T>;
PRI:
EoVLTree<T> m_e;
// 通常はm_eを指すが、VLSubTree( EoVLTree<T>& )や
// VLSubTree( CST IToVLTree<T>& )経由で呼び出された場合のみ
// 参照元のNodeを指す。
EoVLTree<T>* m_p_root;
uint m_size;
PRI:
// Tは引数0のコンストラクタを持つクラスのみ許容。
// デストラクタがdelete演算子を呼ばないため、VLTreeかForest経由でしか呼び出してはいけない。
INL VLSubTree();
// Tは引数0のコンストラクタを持つクラスのみ許容。
// rootのみの木に引数たちをpush_RightMostして高々m_size == 1の木を構築する。
// デストラクタがdelete演算子を呼ばないため、VLTree経由でしか呼び出してはいけない。
TMP <TYP Arg1 , TYP... Arg2> INL VLSubTree( CST Arg1& , CST Arg2&... );
// Tが引数0のコンストラクタを持たないクラスの場合に使用。
// デストラクタがdelete演算子を呼ばないため、VLTree経由でしか呼び出してはいけない。
// TMP <TYP Arg> INL VLSubTree( CST WrappedType<Arg>& t );
// 構築された木への変更がコピー元へは反映されない。
// デストラクタがdelete演算子を呼ばないため、VLTree経由でしか呼び出してはいけない。
// Substriture_Bodyを経由するため、自身への変更が引数へは反映されない。
// 引数をVLSubCSTTree<T>にしたものを定義して委譲するとループしてしまう。
INL VLSubTree( CST VLSubTree<T>& );
// 構築された木への変更がコピー元へは反映される。
// VLTreeを経由しなくても呼び出して良い。
// VLTreeを経由してはならない。
INL VLSubTree( EoVLTree<T>& );
INL VLSubTree( CST IToVLTree<T>& );
// 構築された木への変更がコピー元へは反映されない。
// デストラクタがdelete演算子を呼ばないため、VLTree経由でしか呼び出してはいけない。
// intはダミー引数。
INL VLSubTree( CST_INT_REF , CST EoVLTree<T>& );
INL VLSubTree( CST_INT_REF , CST CSTIToVLTree<T>& );
// 部分木のコピーを構築してpush_RightMostNodeで挿入するため、自身への変更が引数へは反映されない。
// LeafToTreeとpush_RightMostとConcatenateの相互再帰。
// m_size == 0の時しか呼んではいけない。
void LeafToTree( CST VLSubTree<T>& );
// 新たにRightMostNodeを構築し、そこを部分木のRootとして結合する。
// 構築された木への変更がコピー元へ反映される。
// Forest経由でしか呼び出してはいけない。
void Graft( VLSubTree<T>& );
PUB:
virtual ~VLSubTree() = default;
// Substriture_Bodyを経由するため、引数が自身と独立でさえあれば、自身への変更が引数へは反映されない。
// CutBranchesを呼び出すため、引数が自身と独立でない場合は、自身への変更が引数へ反映されうる上に、Segmentation Faultを引き起こす可能性がある。
// 引数をVLTree<T>にしたものを定義して呼び出すとループしてしまう。
VLSubTree<T>& OPR=( CST VLSubTree<T>& );
INL CST_UINT_REF size() CST NEX;
INL void CutBranches();
INL bool IsLeaf() CST NEX;
// 部分木を構築して返すため、部分木への変更が自身へも反映される。
INL VLSubTree<T> LeftMostSubTree();
INL VLSubTree<T> RightMostSubTree();
// 部分木のコピーを構築して返すため、部分木への変更が自身へは反映されない。
INL VLTree<T> LeftMostSubTreeCopy() CST;
INL VLTree<T> RightMostSubTreeCopy() CST;
// LeafToTreeとpush_RightMostとConcatenateの相互再帰。
INL void push_RightMost() CST NEX;
TMP <TYP Arg1 , TYP... Arg2> void push_RightMost( CST Arg1& , CST Arg2&... );
TMP <TYP... Args> void push_RightMost( CST VLTree<T>& , CST Args&... );
TMP <TYP Arg> void push_LeftMost( CST Arg& );
void pop_RightMost();
void pop_LeftMost();
// m_size == 1（特にm_p_root->m_leftmost_node== m_p_root->m_rightmost_node）の時しか呼んではならない。
// m_p_rootはdelete可能とは限らないため、代わりに値のすげかえを行い実際にdeleteされるのはm_p_rootでなくm_p_root->m_leftmost_nodeである。
// 従って特にiteratorの処理に注意が必要。
void pop_Root();
using iterator = IToVLTree<T>;
using CST_iterator = CSTIToVLTree<T>;
// *thisがCSTである場合に確実にCST_iterator返しをするために、iterator返しは非CSTにする必要がある。
INL iterator LeftMostNode() NEX;
INL CST_iterator LeftMostNode() CST NEX;
INL iterator RightMostNode() NEX;
INL CST_iterator RightMostNode() CST NEX;
iterator LeftMostLeaf() NEX;
CST_iterator LeftMostLeaf() CST NEX;
iterator RightMostLeaf() NEX;
CST_iterator RightMostLeaf() CST NEX;
INL iterator Root() NEX;
INL CST_iterator Root() CST NEX;
TMP <TYP... Args> INL iterator GetIterator( CST Args&... );
TMP <TYP... Args> INL CST_iterator GetIterator( CST Args&... ) CST;
// iteratorの右に新たなLeafを構築する。
TMP <TYP Arg> void insert( CST iterator& , CST Arg& );
// RightMostである場合はrootへのイテレータを返す。
iterator erase( iterator& );
// RootやNodeのラベルに直接読み書きを行う。
INL CST T& GetRoot() CST NEX;
INL T& RefRoot() NEX;
INL void SetRoot( CST T& );
TMP <TYP... Args> INL CST T& GetNode( CST Args&... ) CST;
// 部分木を構築して返すため、部分木への変更が自身へも反映される。
VLSubTree<T> OPR[]( CST_UINT_REF );
VLSubTree<T> OPR[]( iterator& );
// 部分木のコピーを構築して返すため、部分木への変更が自身へは反映されない。
VLTree<T> OPR[]( CST CST_iterator& ) CST;
VLTree<T> GetBranchCopy( CST_UINT_REF ) CST;
VLTree<T> GetBranchCopy( CST iterator& ) CST;
VLTree<T> GetBranchCopy( CST CST_iterator& ) CST;
// 現在のRightMostNodeやiteratorの指す位置を部分木のRootとしてコピーを構築する。
// 構築された木への変更がコピー元へは反映されない。
// LeafToTreeとpush_RightMostとConcatenateの相互再帰。
void Concatenate( CST VLTree<T>& );
void Concatenate( CST iterator& , CST VLTree<T>& );
bool CheckContain( CST iterator& ) CST NEX;
bool CheckContain( CST CST_iterator& ) CST NEX;
string Display() CST;
};
TMP <TYP T> bool OPR==( CST VLTree<T>& , CST VLTree<T>& );
TMP <TYP T> INL bool OPR!=( CST VLTree<T>& , CST VLTree<T>& );
TMP <TYP T> INL VLSubTree<T>::VLSubTree() : m_e() , m_p_root( &m_e ) , m_size( 0 ) {}
TMP <TYP T> TMP <TYP Arg1 , TYP... Arg2> INL VLSubTree<T>::VLSubTree( CST Arg1& t0 , CST Arg2&... t1 ) : VLSubTree<T>() { push_RightMost( t0 , t1... ); }
// TMP <TYP T> TMP <TYP Arg> INL VLSubTree<T>::VLSubTree( CST WrappedType<Arg>& t ) : m_e( t.Get() ) , m_p_root( &m_e ) , m_size( 0 ) {}
TMP <TYP T> INL VLSubTree<T>::VLSubTree( CST VLSubTree<T>& a ) : m_e( a.m_e.m_t ) , m_p_root( &m_e ) , m_size( 0 ) { LeafToTree( a ); }
TMP <TYP T>
VLSubTree<T>::VLSubTree( EoVLTree<T>& e ) :
m_e( e ) , m_p_root( &e ) , m_size( 0 )
{
EoVLTree<T>* p = m_p_root->m_leftmost_node;
if( p != m_p_root ){
m_size++;
EoVLTree<T>* CST p_rightmost = m_p_root->m_rightmost_node;
while( p != p_rightmost ){
p = p->m_right_branch;
m_size++;
}
}
}
TMP <TYP T> INL VLSubTree<T>::VLSubTree( CST IToVLTree<T>& itr ) : VLSubTree( *( itr.m_p ) ) {}
TMP <TYP T>
VLSubTree<T>::VLSubTree( CST_INT_REF dummy , CST EoVLTree<T>& e ) :
m_e( e.m_t ) , m_p_root( &m_e ) , m_size( 0 )
{
CST EoVLTree<T>* p = e.m_leftmost_node;
CST EoVLTree<T>* CST p_rightmost = e.m_rightmost_node;
bool b = ( p != &e );
while( b ){
push_RightMost( VLTree<T>( dummy , *p ) );
b = ( p != p_rightmost );
p = p->m_right_branch;
}
}
TMP <TYP T> INL VLSubTree<T>::VLSubTree( CST_INT_REF dummy , CST CSTIToVLTree<T>& itr ) : VLSubTree( dummy , *( itr.m_p ) ) {}
TMP <TYP T>
VLSubTree<T>& VLSubTree<T>::OPR=( CST VLSubTree<T>& a )
{
if( this != &a ){
CutBranches();
LeafToTree( a );
}
RET *this;
}
TMP <TYP T>
void VLSubTree<T>::LeafToTree( CST VLSubTree<T>& a )
{
m_p_root->m_t = a.m_p_root->m_t;
EoVLTree<T>* p = a.m_p_root->m_leftmost_node;
CST_UINT_REF N = a.m_size;
for( uint n = 0 ; n < N ; n++ ){
push_RightMost( VLTree<T>( 0 , *p ) );
p = p->m_right_branch;
}
RET;
}
TMP <TYP T> INL CST_UINT_REF VLSubTree<T>::size() CST NEX { RET m_size; }
TMP <TYP T> INL void VLSubTree<T>::CutBranches(){ while( m_size > 0 ) pop_RightMost(); }
TMP <TYP T> INL bool VLSubTree<T>::IsLeaf() CST NEX { RET m_size == 0; }
TMP <TYP T> INL VLSubTree<T> VLSubTree<T>::LeftMostSubTree() { RET VLSubTree( *( m_p_root->m_leftmost_node ) ); }
TMP <TYP T> INL VLSubTree<T> VLSubTree<T>::RightMostSubTree() { RET VLSubTree( *( m_p_root->m_rightmost_node ) ); }
TMP <TYP T> INL VLTree<T> VLSubTree<T>::LeftMostSubTreeCopy() CST { RET VLTree<T>( 0 , *( m_p_root->m_leftmost_node ) ); }
TMP <TYP T> INL VLTree<T> VLSubTree<T>::RightMostSubTreeCopy() CST { RET VLTree<T>( 0 , *( m_p_root->m_rightmost_node ) ); }
TMP <TYP T> INL void VLSubTree<T>::push_RightMost() CST NEX {}
TMP <TYP T> TMP <TYP Arg1 , TYP... Arg2>
void VLSubTree<T>::push_RightMost( CST Arg1& t0 , CST Arg2&... t1 )
{
auto p = new EoVLTree<T>( t0 );
EoVLTree<T>*& p_rightmost = m_p_root->m_rightmost_node;
if( p_rightmost == m_p_root ){
m_p_root->m_leftmost_node = p;
} else {
p->m_left_branch = p_rightmost;
p_rightmost->m_right_branch = p; 
}
p_rightmost = p;
m_size++;
push_RightMost( t1... );
RET;
}
TMP <TYP T> TMP <TYP... Args>
void VLSubTree<T>::push_RightMost( CST VLTree<T>& t0 , CST Args&... t1 )
{
push_RightMost( t0.m_p_root->m_t );
Concatenate( t0 );
push_RightMost( t1... );
RET;
}
TMP <TYP T> TMP <TYP Arg>
void VLSubTree<T>::push_LeftMost( CST Arg& t )
{
auto p = new EoVLTree<T>( t );
EoVLTree<T>*& p_leftmost = m_p_root->m_leftmost_node;
if( p_leftmost == m_p_root ){
m_p_root->m_rightmost_node = p;
} else {
p->m_right_branch = p_leftmost;
p_leftmost->m_left_branch = p;
}
p_leftmost = p;
m_size++;
RET;
}
TMP <TYP T>
void VLSubTree<T>::pop_RightMost()
{
// if( m_size == 0 ){
// ERR_CALL;
// }
EoVLTree<T>* p_rightmost = m_p_root->m_rightmost_node;
VLSubTree<T> t{ *p_rightmost };
t.CutBranches();
if( m_size == 1 ){
m_p_root->m_leftmost_node = m_p_root;
m_p_root->m_rightmost_node = m_p_root;
} else {
EoVLTree<T>* CST& p_rightmost_prev = p_rightmost->m_left_branch;
m_p_root->m_rightmost_node = p_rightmost_prev;
p_rightmost_prev->m_right_branch = p_rightmost_prev;
}
delete p_rightmost;
m_size--;
RET;
}
TMP <TYP T>
void VLSubTree<T>::pop_LeftMost()
{
// if( m_size == 0 ){
// ERR_CALL;
// }
EoVLTree<T>* p_leftmost = m_p_root->m_leftmost_node;
VLSubTree<T> t{ *p_leftmost };
t.CutBranches();
if( m_size == 1 ){
m_p_root->m_leftmost_node = m_p_root;
m_p_root->m_rightmost_node = m_p_root;
} else {
EoVLTree<T>* CST& p_leftmost_next = p_leftmost->m_right_branch;
m_p_root->m_leftmost_node = p_leftmost_next;
p_leftmost_next->m_left_branch = p_leftmost_next;
}
delete p_leftmost;
m_size--;
RET;
}
TMP <TYP T>
void VLSubTree<T>::pop_Root()
{
// if( m_size != 1 ){
// ERR_CALL;
// }
EoVLTree<T>* p_unique_node = m_p_root->m_leftmost_node;
m_p_root->m_t = p_unique_node->m_t;
m_p_root->m_leftmost_node = p_unique_node->m_leftmost_node;
m_p_root->m_rightmost_node = p_unique_node->m_rightmost_node;
delete p_unique_node;
EoVLTree<T>* p_node = m_p_root->m_leftmost_node;
m_size = 0;
if( p_node != m_p_root ){
m_size++;
while( p_node != p_node->m_right_branch ){
p_node = p_node->m_right_branch;
m_size++;
}
}
RET;
}
TMP <TYP T> INL TYP VLSubTree<T>::iterator VLSubTree<T>::LeftMostNode() NEX { RET IToVLTree<T>( m_p_root->m_leftmost_node ); }
TMP <TYP T> INL TYP VLSubTree<T>::CST_iterator VLSubTree<T>::LeftMostNode() CST NEX { RET CSTIToVLTree<T>( m_p_root->m_leftmost_node ); }
TMP <TYP T> INL TYP VLSubTree<T>::iterator VLSubTree<T>::RightMostNode() NEX { RET IToVLTree<T>( m_p_root->m_rightmost_node ); }
TMP <TYP T> INL TYP VLSubTree<T>::CST_iterator VLSubTree<T>::RightMostNode() CST NEX { RET CSTIToVLTree<T>( m_p_root->m_rightmost_node ); }
TMP <TYP T>
TYP VLSubTree<T>::iterator VLSubTree<T>::LeftMostLeaf() NEX
{
EoVLTree<T>* p = m_p_root->m_leftmost_node;
while( p != p->m_leftmost_node ){
p = p->m_leftmost_node;
}
RET IToVLTree<T>( p );
}
TMP <TYP T>
TYP VLSubTree<T>::CST_iterator VLSubTree<T>::LeftMostLeaf() CST NEX
{
CST EoVLTree<T>* p = m_p_root->m_leftmost_node;
while( p != p->m_leftmost_node ){
p = p->m_leftmost_node;
}
RET CSTIToVLTree<T>( p );
}
TMP <TYP T>
TYP VLSubTree<T>::iterator VLSubTree<T>::RightMostLeaf() NEX
{
EoVLTree<T>* p = m_p_root->m_rightmost_node;
while( p != p->m_rightmost_node ){
p = p->m_rightmost_node;
}
RET IToVLTree<T>( p );
}
TMP <TYP T>
TYP VLSubTree<T>::CST_iterator VLSubTree<T>::RightMostLeaf() CST NEX
{
CST EoVLTree<T>* p = m_p_root->m_rightmost_node;
while( p != p->m_rightmost_node ){
p = p->m_rightmost_node;
}
RET CSTIToVLTree<T>( p );
}
TMP <TYP T> INL TYP VLSubTree<T>::iterator VLSubTree<T>::Root() NEX { RET IToVLTree<T>( m_p_root ); }
TMP <TYP T> INL TYP VLSubTree<T>::CST_iterator VLSubTree<T>::Root() CST NEX { RET CSTIToVLTree<T>( m_p_root ); }
TMP <TYP T> TMP <TYP... Args> INL TYP VLSubTree<T>::iterator VLSubTree<T>::GetIterator( CST Args&... args ) { RET Root().Shift( args... ); }
TMP <TYP T> TMP <TYP... Args> INL TYP VLSubTree<T>::CST_iterator VLSubTree<T>::GetIterator( CST Args&... args ) CST { RET Root().Shift( args... ); }
TMP <TYP T> TMP <TYP Arg>
void VLSubTree<T>::insert( CST TYP VLSubTree<T>::iterator& itr , CST Arg& t )
{
EoVLTree<T>* CST& p0 = itr.m_p;
EoVLTree<T>* CST& p1 = p0->m_right_branch;
auto p = new EoVLTree<T>( t , p0 , p1 );
p1->m_left_branch = p;
p0->m_right_branch = p;
m_size++;
RET;
}
TMP <TYP T>
TYP VLSubTree<T>::iterator VLSubTree<T>::erase( TYP VLSubTree<T>::iterator& itr )
{
EoVLTree<T>* CST p = itr.m_p;
EoVLTree<T>* CST p0 = p->m_left_branch;
EoVLTree<T>* CST p1 = p->m_right_branch;
if( ! itr.IsLeaf() ){
VLSubTree<T> t_sub{ *p };
t_sub.CutBranches();
}
if( p0 != p ){
if( p != p1 ){
itr++;
p0->m_right_branch = p1;
p1->m_left_branch = p0;
} else {
itr--;
p0->m_right_branch = p0;
m_p_root->m_rightmost_node = p0;
}
} else {
if( p != p1 ){
itr++;
p1->m_left_branch = p1;
m_p_root->m_leftmost_node = p1;
} else {
itr = Root();
m_p_root->m_leftmost_node = m_p_root;
m_p_root->m_rightmost_node = m_p_root;
}
}
delete p;
m_size--;
RET itr;
}
TMP <TYP T> INL CST T& VLSubTree<T>::GetRoot() CST NEX { RET m_p_root->m_t; }
TMP <TYP T> INL T& VLSubTree<T>::RefRoot() NEX { RET m_p_root->m_t; }
TMP <TYP T> INL void VLSubTree<T>::SetRoot( CST T& t ){ m_p_root->m_t = t; }
TMP <TYP T> TMP <TYP... Args> INL CST T& VLSubTree<T>::GetNode( CST Args&... args ) CST { RET ACCESS( GetIterator( args... ) ); }
TMP <TYP T>
VLSubTree<T> VLSubTree<T>::OPR[]( CST_UINT_REF i )
{
if( i <= m_size / 2 ){
EoVLTree<T>* p = m_p_root->m_leftmost_node;
for( uint n = 0 ; n < i ; n++ ){
p = p->m_right_branch;
}
RET VLSubTree<T>( *p );
}
EoVLTree<T>* p = m_p_root->m_rightmost_node;
for( uint n = m_size - 1 ; n > i ; n-- ){
p = p->m_left_branch;
}
RET VLSubTree<T>( *p );
}
TMP <TYP T>
VLSubTree<T> VLSubTree<T>::OPR[]( TYP VLSubTree<T>::iterator& itr )
{
RET VLSubTree<T>( *( itr.m_p ) );
}
TMP <TYP T>
VLTree<T> VLSubTree<T>::OPR[]( CST TYP VLSubTree<T>::CST_iterator& itr ) CST
{
RET VLTree<T>( 0 , itr.m_p );
}
TMP <TYP T>
VLTree<T> VLSubTree<T>::GetBranchCopy( CST_UINT_REF i ) CST
{
if( i <= m_size / 2 ){
CST EoVLTree<T>* p = m_p_root->m_leftmost_node;
for( uint n = 0 ; n < i ; n++ ){
p = p->m_right_branch;
}
RET VLTree<T>( 0 , *p );
}
CST EoVLTree<T>* p = m_p_root->m_rightmost_node;
for( uint n = m_size - 1 ; n > i ; n-- ){
p = p->m_left_branch;
}
RET VLTree<T>( 0 , *p );
}
TMP <TYP T>
VLTree<T> VLSubTree<T>::GetBranchCopy( CST TYP VLSubTree<T>::iterator& itr ) CST
{
RET VLTree<T>( 0 , *( itr.m_p ) );
}
TMP <TYP T>
VLTree<T> VLSubTree<T>::GetBranchCopy( CST TYP VLSubTree<T>::CST_iterator& itr ) CST
{
RET VLTree<T>( 0 , *( itr.m_p ) );
}
TMP <TYP T> 
void VLSubTree<T>::Concatenate( CST VLTree<T>& t )
{
EoVLTree<T>* CST p_rightmost = m_p_root->m_rightmost_node;
if( m_p_root == p_rightmost ){
LeafToTree( t );
} else {
VLSubTree<T>( *p_rightmost ).LeafToTree( t );
}
RET;
}
TMP <TYP T> 
void VLSubTree<T>::Concatenate( CST TYP VLSubTree<T>::iterator& itr , CST VLTree<T>& t )
{
EoVLTree<T>* CST p = itr.m_p;
if( m_p_root == p ){
LeafToTree( t );
} else {
VLSubTree<T>( *p ).LeafToTree( t );
}
RET;
}
TMP <TYP T> 
void VLSubTree<T>::Graft( VLSubTree<T>& t )
{
EoVLTree<T>*& p_rightmost = m_p_root->m_rightmost_node;
if( m_p_root == p_rightmost ){
p_rightmost = m_p_root->m_leftmost_node = t.m_p_root;
} else {
t.m_p_root->m_left_branch = p_rightmost;
p_rightmost = p_rightmost->m_right_branch = t.m_p_root;
}
RET;
}
TMP <TYP T>
bool VLSubTree<T>::CheckContain( CST iterator& itr ) CST NEX
{
auto p0 = itr.m_p;
auto p1 = m_p_root->m_leftmost_node;
for( uint i = 0 ; i < m_size ; i++ ){
if( p0 == p1 ){
RET true;
}
p1 = p1->m_right_branch;
}
RET false;
}
TMP <TYP T>
bool VLSubTree<T>::CheckContain( CST CST_iterator& itr ) CST NEX
{
auto p0 = itr.m_p;
auto p1 = m_p_root->m_leftmost_node;
for( uint i = 0 ; i < m_size ; i++ ){
if( p0 == p1 ){
RET true;
}
p1 = p1->m_right_branch;
}
RET false;
}
TMP <TYP T>
string VLSubTree<T>::Display() CST
{
string s = to_string( m_p_root->m_t );
s += "(";
CST EoVLTree<T>* p = m_p_root->m_leftmost_node;
for( uint i = 0 ; i < m_size ; i++ ){
if( i > 0 ){
s += ",";
}
s += VLTree<T>( 0 , *p ).Display();
p = p->m_right_branch;
}
s += ")";
RET s;
}
TMP <TYP T>
bool OPR==( CST VLTree<T>& t1 , CST VLTree<T>& t2 )
{
if( t1.GetRoot() != t2.GetRoot() ){
RET false;
}
if( t1.IsLeaf() ){
RET t2.IsLeaf();
}
if( t2.IsLeaf() ){
RET false;
}
auto itr1 = t1.LeftMostNode();
auto itr2 = t2.LeftMostNode();
while( itr1.IsValid() && itr2.IsValid() ){
if( t1.GetBranchCopy( *itr1 ) != t2.GetBranchCopy( *itr2 ) ){
RET false;
}
itr1++;
itr2++;
}
RET !( itr1.IsValid() || itr2.IsValid() );
}
TMP <TYP T> INL bool OPR!=( CST VLTree<T>& t1 , CST VLTree<T>& t2 ) { RET !( t1 == t2 ); }
TMP <TYP T>
class VLTree :
PUB VLSubTree<T>
{
PUB:
TMP <TYP... Args> INL VLTree( CST Args&... );
VLTree( EoVLTree<T>& ) = delete;
virtual ~VLTree();
TMP <TYP Arg> VLTree<T>& OPR=( CST Arg& );
};
TMP <TYP T> TMP <TYP... Args> INL VLTree<T>::VLTree( CST Args&... t ) : VLSubTree<T>( t... ) {}
TMP <TYP T> VLTree<T>::~VLTree(){ VLSubTree<T>::CutBranches(); }
TMP <TYP T> TMP <TYP Arg>
VLTree<T>& VLTree<T>::OPR=( CST Arg& t )
{
VLSubTree<T>::OPR=( t );
RET *this;
}
TMP <TYP T> class UnionFindForest;
TMP <TYP T> class EoLinkedVector;
TMP <TYP T>
class EoUnionFindForest
{
friend UnionFindForest<T>;
friend EoLinkedVector<EoUnionFindForest<T> >;
PRI:
VLSubTree<T> m_node;
uint m_pred_node;
uint m_root;
uint m_depth;
PRI:
INL EoUnionFindForest();
INL EoUnionFindForest( CST T& t , CST_UINT_REF num );
INL EoUnionFindForest( EoUnionFindForest&& e );
};
TMP <TYP T> INL EoUnionFindForest<T>::EoUnionFindForest() : m_node() , m_pred_node( 0 ) , m_root( 0 ) , m_depth( 0 ) {}
TMP <TYP T> INL EoUnionFindForest<T>::EoUnionFindForest( CST T& t , CST_UINT_REF num ) : m_node() , m_pred_node( num ) , m_root( num ) , m_depth( 0 ) { m_node.SetRoot( t ); }
TMP <TYP T> INL EoUnionFindForest<T>::EoUnionFindForest( EoUnionFindForest<T>&& e ) : m_node() , m_pred_node( move( e.m_pred_node ) ) , m_root( move( e.m_root ) ) , m_depth( move( e.m_depth ) ) { m_node.SetRoot( move( e.m_node.m_p_root->m_t ) ); }
TMP <TYP T>
class UnionFindForest :
PUB LinkedVector<EoUnionFindForest<T> >
{
PUB:
// EoUnionFindForest<T>::m_nodeはVLSubTree<T>型でありポインタをメンバに持つため
// 予め最大要素数を固定しないといけない。
INL UnionFindForest( CST_UINT_REF max_size );
// num番目のNodeをRootとする部分木を構築する。
// INL CST VLSubTree<T>& GetSubTree( CST_UINT_REF num ) CST;
INL VLSubTree<T>& GetSubTree( CST_UINT_REF num );
// num番目のNodeのPredecessor Nodeを返す。
INL CST_UINT_REF GetPredecessorNode( CST_UINT_REF num ) CST;
// num番目のNodeのRootを計算して返す。
CST_UINT_REF GetRootOfNode( CST_UINT_REF num );
// num番目のRootを返す。
uint GetRoot( CST_UINT_REF num ) CST;
// num番目のNodeに格納された値への参照を返す。
INL CST T& OPR[]( CST uint& num ) CST;
INL T& OPR[]( CST uint& num );
INL CST_UINT_REF GetSizeOfNode() CST NEX;
INL CST_UINT_REF GetSizeOfRoot() CST NEX;
// 最初に指定したmax_sizeよりGetSizeOfNode()が大きい場合はサポート外
INL void push_RightMost();
void push_RightMost( CST T& t );
TMP <TYP... ARGS> INL void push_RightMost( CST T& t , CST ARGS&... args );
INL void push_back() = delete;
TMP <TYP U> void push_back( CST U& u ) = delete;
TMP <TYP U , TYP... ARGS> INL void push_back( CST U& u , CST ARGS&... args ) = delete;
INL void SetPreviousLink( CST_UINT_REF i , CST_UINT_REF j ) = delete;
INL void SetNexttLink( CST_UINT_REF i , CST_UINT_REF j ) = delete;
INL CST_UINT_REF GetPreviousLinkIndex( CST_UINT_REF i ) CST = delete;
INL CST_UINT_REF GetNexttLinkIndex( CST_UINT_REF i ) CST = delete;
CST_UINT_REF DeLink( CST_UINT_REF i ) = delete;
void ReLink( CST_UINT_REF i ) = delete;
void Graft( CST_UINT_REF num0 , CST_UINT_REF num1 );
};
TMP <TYP T> INL UnionFindForest<T>::UnionFindForest( CST_UINT_REF max_size ) : LinkedVector<EoUnionFindForest<T> >( max_size ) {}
// TMP <TYP T> INL CST VLSubTree<T>& UnionFindForest<T>::GetSubTree( CST_UINT_REF num ) CST { RET LinkedVector<EoUnionFindForest<T> >::OPR[]( num ).m_node; }
TMP <TYP T> INL VLSubTree<T>& UnionFindForest<T>::GetSubTree( CST_UINT_REF num ) { RET LinkedVector<EoUnionFindForest<T> >::OPR[]( num ).m_node; }
TMP <TYP T> INL CST_UINT_REF UnionFindForest<T>::GetPredecessorNode( CST_UINT_REF num ) CST { RET LinkedVector<EoUnionFindForest<T> >::OPR[]( num ).m_pred_node; }
TMP <TYP T>
CST_UINT_REF UnionFindForest<T>::GetRootOfNode( CST_UINT_REF num )
{
uint& root = LinkedVector<EoUnionFindForest<T> >::OPR[]( num ).m_root;
if( root != LinkedVector<EoUnionFindForest<T> >::OPR[]( root ).m_root ){
root = GetRootOfNode( root );
}
RET root;
}
TMP <TYP T>
uint UnionFindForest<T>::GetRoot( CST_UINT_REF num ) CST
{
auto itr = LinkedVector<EoUnionFindForest<T> >::begin();
for( uint i = 0 ; i < num ; i++ ){
itr++;
}
RET itr.GetIndex();
}
TMP <TYP T> INL CST T& UnionFindForest<T>::OPR[]( CST uint& num ) CST { RET LinkedVector<EoUnionFindForest<T> >::OPR[]( num ).m_node.GetRoot(); }
TMP <TYP T> INL T& UnionFindForest<T>::OPR[]( CST uint& num ) { RET LinkedVector<EoUnionFindForest<T> >::OPR[]( num ).m_node.RefRoot(); }
TMP <TYP T> INL CST_UINT_REF UnionFindForest<T>::GetSizeOfNode() CST NEX { RET LinkedVector<EoUnionFindForest<T> >::GetSizeOfVector(); }
TMP <TYP T> INL CST_UINT_REF UnionFindForest<T>::GetSizeOfRoot() CST NEX { RET LinkedVector<EoUnionFindForest<T> >::GetSizeOfLink(); }
TMP <TYP T> INL void UnionFindForest<T>::push_RightMost() {}
TMP <TYP T>
void UnionFindForest<T>::push_RightMost( CST T& t )
{
EoLinkedVector<EoUnionFindForest<T> >& e = LinkedVector<EoUnionFindForest<T> >::push_back_Body_0();
e.m_t.m_node.SetRoot( t );
e.m_t.m_pred_node = e.m_t.m_root = LinkedVector<EoUnionFindForest<T> >::m_size_of_vector;
LinkedVector<EoUnionFindForest<T> >::push_back_Body_1( e );
RET;
}
TMP <TYP T> TMP <TYP... ARGS> INL void UnionFindForest<T>::push_RightMost( CST T& t , CST ARGS&... args ) { push_RightMost( t ); push_RightMost( args... ); }
TMP <TYP T>
void UnionFindForest<T>::Graft( CST_UINT_REF num0 , CST_UINT_REF num1 )
{
CST_UINT_REF e0_root_index = LinkedVector<EoUnionFindForest<T> >::OPR[]( num0 ).m_root;
CST_UINT_REF e1_root_index = LinkedVector<EoUnionFindForest<T> >::OPR[]( num1 ).m_root;
// if( e0_root_index == e1_root_index ){
// RET;
// }
EoUnionFindForest<T>& e0_root = LinkedVector<EoUnionFindForest<T> >::OPR[]( e0_root_index );
EoUnionFindForest<T>& e1_root = LinkedVector<EoUnionFindForest<T> >::OPR[]( e1_root_index );
// CST uint i0 = ( e0_root.m_depth < e1_root.m_depth ? 0 : 1 );
// CST uint i1 = 1 - i0;
// EoUnionFindForest<T>* CST p_e_root[2] = { &e0_root , &e1_root };
// EoUnionFindForest<T>& root_0 = *( p_e_root[i0] );
// EoUnionFindForest<T>& root_1 = *( p_e_root[i1] );
// if( root_0.m_depth == root_1.m_depth ){
// root_1.m_depth++;
// }
// root_1.m_node.Graft( root_0.m_node );
// LinkedVector<EoUnionFindForest<T> >::DeLink( root_0.m_root );
// root_0.m_root = root_0.m_pred_node = root_1.m_root;
e0_root.m_node.Graft( e1_root.m_node );
LinkedVector<EoUnionFindForest<T> >::DeLink( e1_root.m_root );
e1_root.m_root = e1_root.m_pred_node = e0_root.m_root;
RET;
}
TMP <TYP T> class SqCSTIToVLTree;
TMP <TYP T>
class SqIToVLTree :
  PUB IToVLTree<T>
{
  // キャスト用のコンストラクタにのみ用いる。
  friend SqCSTIToVLTree<T>;
PRI:
  VLArray<IToVLTree<T> > m_itr;
PUB:
  INL SqIToVLTree( CST IToVLTree<T>& );
  INL SqIToVLTree( CST SqIToVLTree<T>& );
  
  SqIToVLTree<T>& OPR=( CST IToVLTree<T>& );
  SqIToVLTree<T>& OPR=( CST SqIToVLTree<T>& );
  void OPR[]( CST int& );
  // INL T& Access_Body( CST char* CST , CST int& , CST char* CST , CST string& , CST uint& ) CST;
  INL T& Ref( CST uint& ) CST;
  INL CST T& Get( CST uint& ) CST;
  INL void pop_front();
  void erase_back( VLSubTree<T>& );
  
  bool CheckContained( CST VLSubTree<T>& ) CST;
  INL uint size() CST NEX;
PRI:
  STT void erase_back_Body( VLSubTree<T>& , SqIToVLTree<T>& );
  STT bool CheckContained_Body( CST VLSubTree<T>& , CST SqIToVLTree<T>& );
};
TMP <TYP T>
class SqCSTIToVLTree :
  PUB CSTIToVLTree<T>
{
PRI:
  VLArray<CSTIToVLTree<T> > m_itr;
PUB:
  INL SqCSTIToVLTree( CST CSTIToVLTree<T>& );
  INL SqCSTIToVLTree( CST SqCSTIToVLTree<T>& );
  SqCSTIToVLTree( CST SqIToVLTree<T>& );
  
  SqCSTIToVLTree<T>& OPR=( CST CSTIToVLTree<T>& );
  SqCSTIToVLTree<T>& OPR=( CST SqCSTIToVLTree<T>& );
  void OPR[]( CST int& );
  // INL CST T& Access_Body( CST char* CST , CST int& , CST char* CST , CST string& , CST uint& ) CST;
  INL CST T& Get( CST uint& ) CST;
  INL void pop_front();
  bool CheckContained( CST VLSubTree<T>& ) CST;
  INL uint size() CST NEX;
PRI:
  STT bool CheckContained_Body( CST VLSubTree<T>& , CST SqCSTIToVLTree<T>& );
};
// SqIToVLTree
TMP <TYP T> INL SqIToVLTree<T>::SqIToVLTree( CST IToVLTree<T>& itr ) : IToVLTree<T>( itr ) , m_itr(){}
TMP <TYP T> INL SqIToVLTree<T>::SqIToVLTree( CST SqIToVLTree<T>& itr ) : IToVLTree<T>( itr ) , m_itr( itr.m_itr ){}
TMP <TYP T>
SqIToVLTree<T>& SqIToVLTree<T>::OPR=( CST IToVLTree<T>& itr )
{
  IToVLTree<T>::OPR=( itr );
  m_itr.clear();
  RET *this;
}
TMP <TYP T>
SqIToVLTree<T>& SqIToVLTree<T>::OPR=( CST SqIToVLTree<T>& itr )
{
  IToVLTree<T>::OPR=( itr );
  m_itr = itr.m_itr;
  RET *this;
}
TMP <TYP T>
void SqIToVLTree<T>::OPR[]( CST int& i )
{
  if( i == 0 ){
    IToVLTree<T>::OPR=( m_itr.back() );
    m_itr.pop_back();
  } else {
    m_itr.push_back( *this );
    IToVLTree<T>::OPR[]( i );
  }
  RET;
}
TMP <TYP T> INL T& SqIToVLTree<T>::Ref( CST uint& i ) CST { RET i == m_itr.size() ? IToVLTree<T>::OPR*() : *( m_itr[i] ); }
TMP <TYP T> INL CST T& SqIToVLTree<T>::Get( CST uint& i ) CST { RET i == m_itr.size() ? IToVLTree<T>::OPR*() : *( m_itr[i] ); }
TMP <TYP T> INL void SqIToVLTree<T>::pop_front(){ m_itr.pop_front(); }
TMP <TYP T>
void SqIToVLTree<T>::erase_back( VLSubTree<T>& t )
{
  SqIToVLTree<T> itr_copy = *this;
  if( IToVLTree<T>::IsRightMost() ){
    if( IToVLTree<T>::IsLeftMost() ){
      OPR[]( 0 );
    } else {
      IToVLTree<T>::OPR--( 0 );
    }
  } else {
    IToVLTree<T>::OPR++( 0 );
  }
  erase_back_Body( t , itr_copy );
  RET;
}
TMP <TYP T>
void SqIToVLTree<T>::erase_back_Body( VLSubTree<T>& t , SqIToVLTree<T>& itr )
{
  CST uint& L = itr.size();
  if( L == 2 ){
    t.erase( itr );
  } else {
    itr.pop_front();
    VLSubTree<T> t_sub = t[ ( itr.m_itr ).front() ];
    erase_back_Body( t_sub , itr );
  }
  RET;
}
TMP <TYP T>
bool SqIToVLTree<T>::CheckContained( CST VLSubTree<T>& t ) CST
{
  if( m_itr.empty() ){
    RET true;
  }
  SqIToVLTree<T> itr_copy = *this;
  itr_copy.pop_front();
  RET CheckContained_Body( t , itr_copy );
}
TMP <TYP T>
bool SqIToVLTree<T>::CheckContained_Body( CST VLSubTree<T>& t , CST SqIToVLTree<T>& itr )
{
  if( ( itr.m_itr ).empty() ){
    RET t.CheckContain( itr );
  }
  CST IToVLTree<T>& itr_front = ( itr.m_itr ).front();
  if( t.CheckContain( itr_front ) ){
    CST VLSubTree<T> t_sub{ itr_front };
    SqIToVLTree<T> itr_copy = itr;
    itr_copy.pop_front();
    RET CheckContained_Body( t_sub , itr_copy );
  }
  RET false;
}
TMP <TYP T> INL uint SqIToVLTree<T>::size() CST NEX { RET m_itr.size() + 1; }
// SqCSTIToVLTree
TMP <TYP T> INL SqCSTIToVLTree<T>::SqCSTIToVLTree( CST CSTIToVLTree<T>& itr ) : CSTIToVLTree<T>( itr ) , m_itr(){}
TMP <TYP T> INL SqCSTIToVLTree<T>::SqCSTIToVLTree( CST SqCSTIToVLTree<T>& itr ) : CSTIToVLTree<T>( itr ) , m_itr( itr.m_itr ){}
TMP <TYP T>
SqCSTIToVLTree<T>::SqCSTIToVLTree( CST SqIToVLTree<T>& itr ) : CSTIToVLTree<T>( itr ) , m_itr()
{
  for( auto itr_itr = ( itr.m_itr ).begin() , itr_itr_e = ( itr.m_itr ).end() ; itr_itr != itr_itr_e ; itr_itr++ ){
    m_itr.push_back( *itr_itr );
  }
}
TMP <TYP T>
SqCSTIToVLTree<T>& SqCSTIToVLTree<T>::OPR=( CST CSTIToVLTree<T>& itr )
{
  CSTIToVLTree<T>::OPR=( itr );
  m_itr.clear();
  RET *this;
}
TMP <TYP T>
SqCSTIToVLTree<T>& SqCSTIToVLTree<T>::OPR=( CST SqCSTIToVLTree<T>& itr )
{
  CSTIToVLTree<T>::OPR=( itr );
  m_itr = itr.m_itr;
  RET *this;
}
TMP <TYP T>
void SqCSTIToVLTree<T>::OPR[]( CST int& i )
{
  if( i == 0 ){
    if( ! m_itr.empty() ){
      CSTIToVLTree<T>::OPR=( m_itr.back() );
      m_itr.pop_back();
    }
  } else {
    m_itr.push_back( *this );
    CSTIToVLTree<T>::OPR[]( i );
  }
  RET;
}
TMP <TYP T> INL CST T& SqCSTIToVLTree<T>::Get( CST uint& i ) CST { RET i == m_itr.size() ? CSTIToVLTree<T>::OPR*() : *( m_itr[i] ); }
TMP <TYP T> INL void SqCSTIToVLTree<T>::pop_front(){ m_itr.pop_front(); }
TMP <TYP T>
bool SqCSTIToVLTree<T>::CheckContained( CST VLSubTree<T>& t ) CST
{
  if( m_itr.empty() ){
    RET true;
  }
  SqCSTIToVLTree<T> itr_copy = *this;
  itr_copy.pop_front();
  RET CheckContained_Body( t , itr_copy );
}
TMP <TYP T>
bool SqCSTIToVLTree<T>::CheckContained_Body( CST VLSubTree<T>& t , CST SqCSTIToVLTree<T>& itr )
{
  if( ( itr.m_itr ).empty() ){
    RET t.CheckContain( itr );
  }
  CST CSTIToVLTree<T>& itr_front = ( itr.m_itr ).front();
  if( t.CheckContain( itr_front ) ){
    CST VLSubTree<T> t_sub{ IToVLTree<T>( const_cast<EoVLTree<T>*>( itr_front.m_p ) ) };
    SqCSTIToVLTree<T> itr_copy = itr;
    itr_copy.pop_front();
    RET CheckContained_Body( t_sub , itr_copy );
  }
  RET false;
}
TMP <TYP T> INL uint SqCSTIToVLTree<T>::size() CST NEX { RET m_itr.size() + 1; }
INL CEX CST int length = 1001;
INL CEX CST int PLUS = -1;
INL CEX CST int MULT = -2;
void SetSyntax( CST string& expr , CST uint& i_init , UnionFindForest<vector<int> >& syntax , uint ( &symbol_to_node )[length] )
{
  uint size = expr.size();
  uint layer = 0;
  uint layer_max = 0;
  uint operator_layer_min = size;
  uint operator_location;
  string operator_symbol;
  string c;
  FOR( i , 0 , size ){
    c = expr.substr( i , 1 );
    if( c == "(" ){
      layer++;
      if( layer_max < layer ){
	layer_max = layer;
      }
    } else if( c == ")" ){
      layer--;
    } else if( c == "$" || c == "&" ){
      if( operator_layer_min > layer ){
	operator_layer_min = layer; 
	operator_location = i;
	operator_symbol = c;
      } else if( operator_layer_min == layer ){
	if( operator_symbol == "&" || c == "$" ){
	  operator_location = i;
	  operator_symbol = c;
	}
      }
    }
  }
  if( operator_layer_min < size ){
    c = expr.substr( operator_location , 1 );
    uint node0 = syntax.GetSizeOfNode();
    symbol_to_node[ operator_location + i_init ] = node0;
    vector<int> v{};
    v.push_back( node0 );
    v.push_back( c == "$" ? PLUS : MULT );
    v.push_back( 0 );
    syntax.push_RightMost( v );
    SetSyntax( expr.substr( 0 , operator_location ) , i_init , syntax , symbol_to_node );
    syntax.Graft( node0 , node0 + 1 );
    uint node1 = syntax.GetSizeOfNode();
    SetSyntax( expr.substr( operator_location + 1 ) , operator_location + 1 + i_init , syntax , symbol_to_node );
    syntax.Graft( node0 , node1 );
  } else {
    vector<int> v{};
    v.push_back( 0 );
    v.push_back( 0 );
    v.push_back( 0 );
    v.push_back( stoi( expr.substr( layer_max , size - layer_max ) ) );
    syntax.push_RightMost( v );
  }
  RET;
}
int main()
{
  UNTIE;
  CEX CST int bound = 301;
  CIN( int , M );
  assert( 1 <= M && M < bound );
  CIN( int , ans );
  assert( 0 <= ans && ans < bound );
  CIN( string , expr );
  uint expr_size = expr.size();
  assert( 1 <= expr_size && expr_size < length );
  UnionFindForest<vector<int> > syntax{ expr_size };
  uint symbol_to_node[length];
  SetSyntax( expr , 0 , syntax , symbol_to_node );
  if( syntax.GetSizeOfNode() == 1 ){
    if( syntax[0].back() == ans ){
      RETURN( expr );
    } else {
      RETURN( -1 );
    }
  }
  SqIToVLTree<vector<int> > itr{ syntax.GetSubTree( syntax.GetRoot( 0 ) ).Root() };
  int value;
  bool passed = false;
  uint left_size;
  uint right_size;
  int left_i;
  int right_j;
  CEX CST uint start_num = 3;
  while( itr.size() != 1 || ! passed ){
    if( passed ){
      if( itr.IsRightMost() ){
	CST vector<int>& right = *itr;
	itr[0];
	itr[1];
	CST vector<int>& left = *itr;
	itr[0];
	bool used[301] = {};
	left_size = left.size();
	right_size = right.size();
	if( ( *itr )[1] == PLUS ){
	  FOR( i , start_num , left_size ){
	    left_i = left[i];
	    FOR( j , start_num , right_size ){
	    right_j = right[j];
	      value = left_i + right_j;
	      if( value <= M ){
		used[value] = true;
	      }
	      value = left_i - right_j;
	      if( 0 <= value ){
		used[value] = true;
	      }
	    }
	  }
	} else {
	  FOR( i , start_num , left_size ){
	    left_i = left[i];
	    FOR( j , start_num , right_size ){
	      right_j = right[j];
	      value = left_i * right_j;
	      if( value <= M ){
		used[value] = true;
	      }
	      if( right_j != 0 ){
		value = left_i / right_j;
		used[value] = true;
	      }
	    }
	  }
	}
	vector<int>& centre = *itr;
	centre.pop_back();
	FOREQ( i , 0 , M ){
	  if( used[i] ){
	    centre.push_back( i );
	  }
	}
	if( centre.size() == start_num ){
	  RETURN( -1 );
	}
      } else {
	itr++;
      }
    } else {
      itr->push_back( 0 );
      itr[1];
    }
    passed = ( itr->size() != start_num );
  }
  vector<int>& answers = *itr;
  bool found = false;
  uint centre_size = answers.size();
  FOR( i , start_num , centre_size ){
    if( answers[i] == ans ){
      found = true;
      break;
    }
  }
  if( ! found ){
    RETURN( -1 );
  }
  CEX CST uint node_num = 0;
  CEX CST uint operator_num = 1;
  CEX CST uint value_num = 2;
  uint answers_size = answers.size();
  while( answers_size > value_num ){
    answers.pop_back();
    answers_size--;
  }
  answers.push_back( ans );
  passed = false;
  int node_to_symbol[length];
  while( itr.size() != 1 || ! passed ){
    if( itr.IsLeaf() || passed ){
      if( itr.IsRightMost() ){
	itr[0];
      } else {
	itr++;
      }
    } else {
      vector<int>& centre = *itr;
      value = centre[value_num];
      itr[1];
      vector<int>& left = *itr;
      left_size = left.size();
      itr++;
      vector<int>& right = *itr;
      right_size = right.size();
      itr--;
      found = false;
      if( centre[operator_num] == PLUS ){
	FOR( i , start_num , left_size ){
	  left_i = left[i];
	  FOR( j , start_num , right_size ){
	    right_j = right[j];
	    if( value == left_i + right_j ){
	      found = true;
	      node_to_symbol[centre[node_num]] = 0;
	    } else if( value == left_i - right_j ){
	      found = true;
	      node_to_symbol[centre[node_num]] = 1;
	    }
	    if( found ){
	      left[value_num] = left_i;
	      right[value_num] = right_j;
	      break;
	    }
	  }
	  if( found ){
	    break;
	  }
	}
      } else {
	FOR( i , start_num , left_size ){
	  left_i = left[i];
	  FOR( j , start_num , right_size ){
	    right_j = right[j];
	    if( value == left_i * right_j ){
	      found = true;
	      node_to_symbol[centre[node_num]] = 0;
	    } else if( right_j != 0 ? value == left_i / right_j : false ){
	      found = true;
	      node_to_symbol[centre[node_num]] = 1;
	    }
	    if( found ){
	      left[value_num] = left_i;
	      right[value_num] = right_j;
	      break;
	    }
	  }
	  if( found ){
	    break;
	  }
	}
      }
      centre_size = centre.size();
      while( centre_size > start_num ){
	centre.pop_back();
	centre_size--;
      }
    }
    passed = ( itr->size() == start_num );
  }
  string c;
  FOR( i , 0 , expr_size ){
    c = expr.substr( i , 1 );
    if( c == "$" ){
      if( node_to_symbol[symbol_to_node[i]] == 0 ){
	cout << "+";
      } else {
	cout << "-";
      }
    } else if( c == "&" ){
      if( node_to_symbol[symbol_to_node[i]] == 0 ){
	cout << "*";
      } else {
	cout << "/";
      }
    } else {
      cout << c;
    }
  }
  RETURN( "" );
}