// #define _GLIBCXX_DEBUG #pragma GCC optimize ( "O3" ) #pragma GCC optimize( "unroll-loops" ) #pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) #include using namespace std; using ll = long long; using uint = unsigned int; #define ATT __attribute__( ( target( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" ) ) ) #define TYPE_OF( VAR ) remove_const::type >::type #define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) #define CEXPR( LL , BOUND , VALUE ) constexpr 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 GETLINE( A ) string A; getline( cin , A ) #define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) #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 FOREQINV( VAR , INITIAL , FINAL ) for( TYPE_OF( INITIAL ) VAR = INITIAL ; VAR >= FINAL ; VAR -- ) #define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) #define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) #define QUIT return 0 #define COUT( ANSWER ) cout << ( ANSWER ) << "\n" #define RETURN( ANSWER ) COUT( ANSWER ); QUIT #define SET_PRECISION( PRECISION ) cout << fixed << setprecision( PRECISION ) #define DOUBLE( PRECISION , ANSWER ) SET_PRECISION << ( ANSWER ) << "\n"; QUIT template inline T Absolute( const T& a ){ return a > 0 ? a : -a; } template inline T Residue( const T& a , const T& p ){ return a >= 0 ? a % p : ( a % p ) + p; } // ARGUMENTの型がintやuintでないように注意 #define POWER( ANSWER , ARGUMENT , EXPONENT ) \ TYPE_OF( ARGUMENT ) ANSWER{ 1 }; \ { \ TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT ); \ TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \ while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \ if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \ ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \ } \ ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER; \ EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \ } \ } \ #define POWER_MOD( ANSWER , ARGUMENT , EXPONENT , MODULO ) \ ll ANSWER{ 1 }; \ { \ ll ARGUMENT_FOR_SQUARE_FOR_POWER = ( MODULO + ( ( ARGUMENT ) % MODULO ) ) % MODULO; \ TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT ); \ while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){ \ if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){ \ ANSWER = ( ANSWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \ } \ ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT_FOR_SQUARE_FOR_POWER * ARGUMENT_FOR_SQUARE_FOR_POWER ) % MODULO; \ EXPONENT_FOR_SQUARE_FOR_POWER /= 2; \ } \ } \ #define FACTORIAL_MOD( ANSWER , ANSWER_INV , INVERSE , MAX_I , LENGTH , MODULO ) \ static ll ANSWER[LENGTH]; \ static ll ANSWER_INV[LENGTH]; \ static ll INVERSE[LENGTH]; \ { \ ll VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \ ANSWER[0] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL; \ FOREQ( i , 1 , MAX_I ){ \ ANSWER[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= i ) %= MODULO; \ } \ ANSWER_INV[0] = ANSWER_INV[1] = INVERSE[1] = VARIABLE_FOR_PRODUCT_FOR_FACTORIAL = 1; \ FOREQ( i , 2 , MAX_I ){ \ ANSWER_INV[i] = ( VARIABLE_FOR_PRODUCT_FOR_FACTORIAL *= INVERSE[i] = MODULO - ( ( ( MODULO / i ) * INVERSE[MODULO % i] ) % MODULO ) ) %= MODULO; \ } \ } \ // 通常の二分探索その1 // EXPRESSIONがANSWERの狭義単調増加関数の時、EXPRESSION >= TARGETを満たす最小の整数を返す。 // 広義単調増加関数を扱いたい時は等号成立の処理を消して続く>に等号を付ける。 #define BS1( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ ll ANSWER; \ { \ ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \ ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \ ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \ ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \ while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \ VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \ break; \ } else { \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \ VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \ } else { \ VARIABLE_FOR_BINARY_SEARCH_L = ANSWER + 1; \ } \ ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \ } \ } \ } \ // 通常の二分探索その2 // EXPRESSIONがANSWERの狭義単調増加関数の時、EXPRESSION <= TARGETを満たす最大の整数を返す。 // 広義単調増加関数を扱いたい時は等号成立の処理を消して続く<に等号を付ける。 #define BS2( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ ll ANSWER; \ { \ ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \ ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \ ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \ ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \ while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \ VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \ break; \ } else { \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH < 0 ){ \ VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \ } else { \ VARIABLE_FOR_BINARY_SEARCH_U = ANSWER - 1; \ } \ ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \ } \ } \ } \ // 通常の二分探索その3 // EXPRESSIONがANSWERの狭義単調減少関数の時、EXPRESSION >= TARGETを満たす最大の整数を返す。 // 広義単調増加関数を扱いたい時は等号成立の処理を消して続く>に等号を付ける。 #define BS3( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ ll ANSWER; \ { \ ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \ ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \ ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \ ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \ while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \ VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \ break; \ } else { \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH > 0 ){ \ VARIABLE_FOR_BINARY_SEARCH_L = ANSWER; \ } else { \ VARIABLE_FOR_BINARY_SEARCH_U = ANSWER - 1; \ } \ ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + 1 + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \ } \ } \ } \ // 通常の二分探索その4 // EXPRESSIONがANSWERの狭義単調減少関数の時、EXPRESSION <= TARGETを満たす最小の整数を返す。 // 広義単調増加関数を扱いたい時は等号成立の処理を消して続く<に等号を付ける。 #define BS4( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ ll ANSWER; \ { \ ll VARIABLE_FOR_BINARY_SEARCH_L = MINIMUM; \ ll VARIABLE_FOR_BINARY_SEARCH_U = MAXIMUM; \ ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \ ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH; \ while( VARIABLE_FOR_BINARY_SEARCH_L != VARIABLE_FOR_BINARY_SEARCH_U ){ \ VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \ break; \ } else { \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH < 0 ){ \ VARIABLE_FOR_BINARY_SEARCH_U = ANSWER; \ } else { \ VARIABLE_FOR_BINARY_SEARCH_L = ANSWER + 1; \ } \ ANSWER = ( VARIABLE_FOR_BINARY_SEARCH_L + VARIABLE_FOR_BINARY_SEARCH_U ) / 2; \ } \ } \ } \ // 二進法の二分探索 // EXPRESSIONがANSWERの狭義単調増加関数の時、EXPRESSION <= TARGETを満たす最大の整数を返す。 #define BBS( ANSWER , MINIMUM , MAXIMUM , EXPRESSION , TARGET ) \ ll ANSWER = MINIMUM; \ { \ ll VARIABLE_FOR_POWER_FOR_BINARY_SEARCH = 1; \ ll VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( MAXIMUM ) - ANSWER; \ while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH <= VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH ){ \ VARIABLE_FOR_POWER_FOR_BINARY_SEARCH *= 2; \ } \ VARIABLE_FOR_POWER_FOR_BINARY_SEARCH /= 2; \ ll VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH = ANSWER; \ while( VARIABLE_FOR_POWER_FOR_BINARY_SEARCH != 0 ){ \ ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH + VARIABLE_FOR_POWER_FOR_BINARY_SEARCH; \ VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH = ( EXPRESSION ) - ( TARGET ); \ if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH == 0 ){ \ VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH = ANSWER; \ break; \ } else if( VARIABLE_FOR_DIFFERENCE_FOR_BINARY_SEARCH < 0 ){ \ VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH = ANSWER; \ } \ VARIABLE_FOR_POWER_FOR_BINARY_SEARCH /= 2; \ } \ ANSWER = VARIABLE_FOR_ANSWER_FOR_BINARY_SEARCH; \ } \ // 圧縮用 #define TE template #define TY typename #define US using #define ST static #define IN inline #define CL class #define PU public #define OP operator #define CE constexpr #define CO const #define NE noexcept #define RE return #define WH while #define VO void #define VE vector #define LI list #define BE begin #define EN end #define SZ size #define MO move #define TH this #define CRI CO int& #define CRUI CO uint& #define CRL CO ll& TE CL EntryOfVLTree{PU:T m_t;EntryOfVLTree* m_left_branch;EntryOfVLTree* m_right_branch;EntryOfVLTree* m_leftmost_node;EntryOfVLTree* m_rightmost_node;IN EntryOfVLTree();TE IN EntryOfVLTree(CO Arg&);TE IN EntryOfVLTree(CO Arg&,EntryOfVLTree* CO&,EntryOfVLTree* CO&);IN EntryOfVLTree(CO EntryOfVLTree&);EntryOfVLTree& OP=(CO EntryOfVLTree&);}; TE IN EntryOfVLTree::EntryOfVLTree(): m_t(),m_left_branch(TH),m_right_branch(TH),m_leftmost_node(TH),m_rightmost_node(TH){}TE TE IN EntryOfVLTree::EntryOfVLTree(CO Arg& t): EntryOfVLTree(t,TH,TH){}TE TE IN EntryOfVLTree::EntryOfVLTree(CO Arg& t,EntryOfVLTree* CO& left_branch,EntryOfVLTree* CO& right_branch): m_t(t),m_left_branch(left_branch),m_right_branch(right_branch),m_leftmost_node(TH),m_rightmost_node(TH){}TE IN EntryOfVLTree::EntryOfVLTree(CO EntryOfVLTree& e): m_t(e.m_t),m_left_branch(e.m_left_branch == &e?TH:e.m_left_branch),m_right_branch(e.m_right_branch == &e?TH:e.m_right_branch),m_leftmost_node(TH),m_rightmost_node(TH){if(e.m_leftmost_node != &e){m_leftmost_node = e.m_leftmost_node;m_rightmost_node = e.m_rightmost_node;}}TE EntryOfVLTree& EntryOfVLTree::OP=(CO EntryOfVLTree& e){m_t = e.m_t;m_left_branch =(e.m_left_branch == &e?TH:e.m_left_branch);m_right_branch =(e.m_right_branch == &e?TH:e.m_right_branch);if(e.m_leftmost_node == &e){m_leftmost_node = m_rightmost_node = TH;}else{m_leftmost_node = e.m_leftmost_node;m_rightmost_node = e.m_rightmost_node;}RE *TH;} TE CL IteratorOfVLTree{PU:EntryOfVLTree* m_p;IN IteratorOfVLTree()NE;IN IteratorOfVLTree(EntryOfVLTree* CO&)NE;IN IteratorOfVLTree(CO IteratorOfVLTree&)NE;IN T& OP*()CO;IN T* OP->()CO;IN IteratorOfVLTree& OP=(CO IteratorOfVLTree&)NE;IteratorOfVLTree& OP++(int)NE;IteratorOfVLTree& OP--(int)NE;IteratorOfVLTree& OP[](CO int&);IteratorOfVLTree& Shift()NE;TE IteratorOfVLTree& Shift(CO int&,CO Args&...);IN bool IsLeaf()CO NE;IN bool IsLeftMost()CO NE;IN bool IsRightMost()CO NE;IN bool IsValid()CO NE;}; TE CL COIteratorOfVLTree{PU:CO EntryOfVLTree* m_p;IN COIteratorOfVLTree()NE;IN COIteratorOfVLTree(CO EntryOfVLTree* CO&)NE;IN COIteratorOfVLTree(CO COIteratorOfVLTree&)NE;IN COIteratorOfVLTree(CO IteratorOfVLTree&)NE;IN CO T& OP*()CO;IN CO T* OP->()CO;IN COIteratorOfVLTree& OP=(CO COIteratorOfVLTree&)NE;IN COIteratorOfVLTree& OP=(CO IteratorOfVLTree&)NE;COIteratorOfVLTree& OP++(int)NE;COIteratorOfVLTree& OP--(int)NE;COIteratorOfVLTree& OP[](CO int&);COIteratorOfVLTree& Shift()NE;TE COIteratorOfVLTree& Shift(CO int&,CO Args&...);IN bool IsLeaf()CO NE;IN bool IsLeftMost()CO NE;IN bool IsRightMost()CO NE;IN bool IsValid()CO NE;ST IN bool Equal(CO IteratorOfVLTree&,CO IteratorOfVLTree&)NE;ST IN bool Equal(CO COIteratorOfVLTree&,CO IteratorOfVLTree&)NE;ST IN bool Equal(CO IteratorOfVLTree&,CO COIteratorOfVLTree&)NE;ST IN bool Equal(CO COIteratorOfVLTree&,CO COIteratorOfVLTree&)NE;}; TE IN IteratorOfVLTree::IteratorOfVLTree()NE:m_p(nullptr){}TE IN IteratorOfVLTree::IteratorOfVLTree(EntryOfVLTree* CO& p)NE:m_p(p){}TE IN IteratorOfVLTree::IteratorOfVLTree(CO IteratorOfVLTree& itr)NE:m_p(itr.m_p){}TE IN T& IteratorOfVLTree::OP*()CO{RE m_p->m_t;}TE IN T* IteratorOfVLTree::OP->()CO{RE &(*(*TH));}TE IN IteratorOfVLTree& IteratorOfVLTree::OP=(CO IteratorOfVLTree& itr)NE{m_p = itr.m_p;RE *TH;}TE IteratorOfVLTree& IteratorOfVLTree::OP++(int)NE{if(m_p == nullptr){RE *TH;}if(m_p == m_p->m_right_branch){m_p = nullptr;}else{m_p = m_p->m_right_branch;}RE *TH;}TE IteratorOfVLTree& IteratorOfVLTree::OP--(int)NE{if(m_p == nullptr){RE *TH;}if(m_p == m_p->m_left_branch){m_p = nullptr;}else{m_p = m_p->m_left_branch;}RE *TH;}TE IteratorOfVLTree& IteratorOfVLTree::OP[](CO int& 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;}}}RE *TH;}TE IteratorOfVLTree& IteratorOfVLTree::Shift()NE{RE *TH;}TE TE IteratorOfVLTree& IteratorOfVLTree::Shift(CO int& n,CO Args&... args){OP[](n);RE Shift(args...);}TE IN bool IteratorOfVLTree::IsLeaf()CO NE{RE(m_p == nullptr)? false :(m_p == m_p->m_leftmost_node);}TE IN bool IteratorOfVLTree::IsLeftMost()CO NE{RE(m_p == nullptr)? false :(m_p == m_p->m_left_branch);}TE IN bool IteratorOfVLTree::IsRightMost()CO NE{RE(m_p == nullptr)? false :(m_p == m_p->m_right_branch);}TE IN bool IteratorOfVLTree::IsValid()CO NE{RE m_p != nullptr;}TE IN COIteratorOfVLTree::COIteratorOfVLTree()NE:m_p(nullptr){}TE IN COIteratorOfVLTree::COIteratorOfVLTree(CO EntryOfVLTree* CO& p)NE:m_p(p){}TE IN COIteratorOfVLTree::COIteratorOfVLTree(CO COIteratorOfVLTree& itr)NE:m_p(itr.m_p){}TE IN COIteratorOfVLTree::COIteratorOfVLTree(CO IteratorOfVLTree& itr)NE:m_p(itr.m_p){}TE IN CO T& COIteratorOfVLTree::OP*()CO{RE m_p->m_t;};TE IN CO T* COIteratorOfVLTree::OP->()CO{RE &(*(*TH));}TE IN COIteratorOfVLTree& COIteratorOfVLTree::OP=(CO COIteratorOfVLTree& itr)NE{m_p = itr.m_p;RE *TH;}TE IN COIteratorOfVLTree& COIteratorOfVLTree::OP=(CO IteratorOfVLTree& itr)NE{m_p = itr.m_p;RE *TH;}TE COIteratorOfVLTree& COIteratorOfVLTree::OP++(int)NE{if(m_p == nullptr){RE *TH;}if(m_p == m_p->m_right_branch){m_p = nullptr;}else{m_p = m_p->m_right_branch;}RE *TH;}TE COIteratorOfVLTree& COIteratorOfVLTree::OP--(int)NE{if(m_p == nullptr){RE *TH;}if(m_p == m_p->m_left_branch){m_p = nullptr;}else{m_p = m_p->m_left_branch;}RE *TH;}TE COIteratorOfVLTree& COIteratorOfVLTree::OP[](CO int& 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;}}RE *TH;}TE COIteratorOfVLTree& COIteratorOfVLTree::Shift()NE{RE *TH;}TE TE COIteratorOfVLTree& COIteratorOfVLTree::Shift(CO int& n,CO Args&... args){OP[](n);RE Shift(args...);}TE IN bool COIteratorOfVLTree::IsLeaf()CO NE{RE(m_p == nullptr)? false :(m_p == m_p->m_leftmost_mode);}TE IN bool COIteratorOfVLTree::IsLeftMost()CO NE{RE(m_p == nullptr)? false :(m_p == m_p->m_left_branch);}TE IN bool COIteratorOfVLTree::IsRightMost()CO NE{RE(m_p == nullptr)? false :(m_p == m_p->m_right_branch);}TE IN bool COIteratorOfVLTree::IsValid()CO NE{RE m_p != nullptr;}TE IN bool COIteratorOfVLTree::Equal(CO IteratorOfVLTree& itr0,CO IteratorOfVLTree& itr1)NE{RE itr0.m_p == itr1.m_p;}TE IN bool COIteratorOfVLTree::Equal(CO COIteratorOfVLTree& itr0,CO IteratorOfVLTree& itr1)NE{RE itr0.m_p == itr1.m_p;}TE IN bool COIteratorOfVLTree::Equal(CO IteratorOfVLTree& itr0,CO COIteratorOfVLTree& itr1)NE{RE itr0.m_p == itr1.m_p;}TE IN bool COIteratorOfVLTree::Equal(CO COIteratorOfVLTree& itr0,CO COIteratorOfVLTree& itr1)NE{RE itr0.m_p == itr1.m_p;}TE IN bool OP==(CO IteratorOfVLTree& itr0,CO IteratorOfVLTree& itr1)NE{RE COIteratorOfVLTree::Equal(itr0,itr1);}TE IN bool OP!=(CO IteratorOfVLTree& itr0,CO IteratorOfVLTree& itr1)NE{RE !(itr0 == itr1);}TE IN bool OP==(CO COIteratorOfVLTree& itr0,CO IteratorOfVLTree& itr1)NE{RE COIteratorOfVLTree::Equal(itr0,itr1);}TE IN bool OP!=(CO COIteratorOfVLTree& itr0,CO IteratorOfVLTree& itr1)NE{RE !(itr0 == itr1);}TE IN bool OP==(CO IteratorOfVLTree& itr0,CO COIteratorOfVLTree& itr1)NE{RE COIteratorOfVLTree::Equal(itr0,itr1);}TE IN bool OP!=(CO IteratorOfVLTree& itr0,CO COIteratorOfVLTree& itr1)NE{RE !(itr0 == itr1);}TE IN bool OP==(CO COIteratorOfVLTree& itr0,CO COIteratorOfVLTree& itr1)NE{RE COIteratorOfVLTree::Equal(itr0,itr1);}TE IN bool OP!=(CO COIteratorOfVLTree& itr0,CO COIteratorOfVLTree& itr1)NE{RE !(itr0 == itr1);} TE CL WrappedType{PU:Arg m_t;TE IN WrappedType(CO ARGS&... args);IN VO Set(CO Arg& t);IN CO Arg& Get()CO NE;}; TE CL WrappedTypes{}; TE TE IN WrappedType::WrappedType(CO ARGS&... args): m_t(args...){}TE IN VO WrappedType::Set(CO Arg& t){m_t = t;}TE IN CO Arg& WrappedType::Get()CO NE{RE m_t;} TE CL VLTree; TE CL VLSubTree{PU:EntryOfVLTree m_e;EntryOfVLTree* m_p_root;uint m_SZ;IN VLSubTree();TE IN VLSubTree(CO Arg1&,CO Arg2&...);TE IN VLSubTree(CO WrappedType& t);IN VLSubTree(CO VLSubTree&);IN VLSubTree(EntryOfVLTree&);IN VLSubTree(CO IteratorOfVLTree&);IN VLSubTree(CO int&,CO EntryOfVLTree&);IN VLSubTree(CO int&,CO COIteratorOfVLTree&);VO LeafToTree(CO VLSubTree&);VO Graft(VLSubTree&);virtual ~VLSubTree()= default;VLSubTree& OP=(CO VLSubTree&);IN CRUI SZ()CO NE;IN VO CutBranches();IN bool IsLeaf()CO NE;IN VLSubTree LeftMostSubTree();IN VLSubTree RightMostSubTree();IN VLTree LeftMostSubTreeCopy()CO;IN VLTree RightMostSubTreeCopy()CO;IN VO push_RightMost()CO NE;TE VO push_RightMost(CO Arg1&,CO Arg2&...);TE VO push_RightMost(CO VLTree&,CO Args&...);TE VO push_LeftMost(CO Arg&);VO pop_RightMost();VO pop_LeftMost();VO pop_Root();US iterator = IteratorOfVLTree;US CO_iterator = COIteratorOfVLTree;IN iterator LeftMostNode()NE;IN CO_iterator LeftMostNode()CO NE;IN iterator RightMostNode()NE;IN CO_iterator RightMostNode()CO NE;iterator LeftMostLeaf()NE;CO_iterator LeftMostLeaf()CO NE;iterator RightMostLeaf()NE;CO_iterator RightMostLeaf()CO NE;IN iterator Root()NE;IN CO_iterator Root()CO NE;TE IN iterator GetIterator(CO Args&...);TE IN CO_iterator GetIterator(CO Args&...)CO;TE VO insert(CO iterator&,CO Arg&);iterator erase(iterator&);IN CO T& GetRoot()CO NE;IN T& RefRoot()NE;IN VO SetRoot(CO T&);TE IN CO T& GetNode(CO Args&...)CO;VLSubTree OP[](CRUI);VLSubTree OP[](iterator&);VLTree OP[](CO CO_iterator&)CO;VLTree GetBranchCopy(CRUI)CO;VLTree GetBranchCopy(CO iterator&)CO;VLTree GetBranchCopy(CO CO_iterator&)CO;VO Concatenate(CO VLTree&);VO Concatenate(CO iterator&,CO VLTree&);bool CheckContain(CO iterator&)CO NE;bool CheckContain(CO CO_iterator&)CO NE;string Display()CO;}; TE IN VLSubTree::VLSubTree(): m_e(),m_p_root(&m_e),m_SZ(0){}TE TE IN VLSubTree::VLSubTree(CO Arg1& t0,CO Arg2&... t1): VLSubTree(){push_RightMost(t0,t1...);}TE TE IN VLSubTree::VLSubTree(CO WrappedType& t): m_e(t.Get()),m_p_root(&m_e),m_SZ(0){}TE IN VLSubTree::VLSubTree(CO VLSubTree& a): m_e(a.m_e.m_t),m_p_root(&m_e),m_SZ(0){LeafToTree(a);}TE VLSubTree::VLSubTree(EntryOfVLTree& e):m_e(e),m_p_root(&e),m_SZ(0){EntryOfVLTree* p = m_p_root->m_leftmost_node;if(p != m_p_root){m_SZ++;EntryOfVLTree* CO p_rightmost = m_p_root->m_rightmost_node;WH(p != p_rightmost){p = p->m_right_branch;m_SZ++;}}}TE IN VLSubTree::VLSubTree(CO IteratorOfVLTree& itr): VLSubTree(*(itr.m_p)){}TE VLSubTree::VLSubTree(CO int& dummy,CO EntryOfVLTree& e):m_e(e.m_t),m_p_root(&m_e),m_SZ(0){CO EntryOfVLTree* p = e.m_leftmost_node;CO EntryOfVLTree* CO p_rightmost = e.m_rightmost_node;bool b =(p != &e);WH(b){push_RightMost(VLTree(dummy,*p));b =(p != p_rightmost);p = p->m_right_branch;}}TE IN VLSubTree::VLSubTree(CO int& dummy,CO COIteratorOfVLTree& itr): VLSubTree(dummy,*(itr.m_p)){}TE VLSubTree& VLSubTree::OP=(CO VLSubTree& a){if(TH != &a){CutBranches();LeafToTree(a);}RE *TH;}TE VO VLSubTree::LeafToTree(CO VLSubTree& a){m_p_root->m_t = a.m_p_root->m_t;EntryOfVLTree* p = a.m_p_root->m_leftmost_node;CRUI N = a.m_SZ;for(uint n = 0;n < N;n++){push_RightMost(VLTree(0,*p));p = p->m_right_branch;}RE;}TE IN CRUI VLSubTree::SZ()CO NE{RE m_SZ;}TE IN VO VLSubTree::CutBranches(){WH(m_SZ > 0)pop_RightMost();}TE IN bool VLSubTree::IsLeaf()CO NE{RE m_SZ == 0;}TE IN VLSubTree VLSubTree::LeftMostSubTree(){RE VLSubTree(*(m_p_root->m_leftmost_node));}TE IN VLSubTree VLSubTree::RightMostSubTree(){RE VLSubTree(*(m_p_root->m_rightmost_node));}TE IN VLTree VLSubTree::LeftMostSubTreeCopy()CO{RE VLTree(0,*(m_p_root->m_leftmost_node));}TE IN VLTree VLSubTree::RightMostSubTreeCopy()CO{RE VLTree(0,*(m_p_root->m_rightmost_node));}TE IN VO VLSubTree::push_RightMost()CO NE{}TE TE VO VLSubTree::push_RightMost(CO Arg1& t0,CO Arg2&... t1){auto p = new EntryOfVLTree(t0);EntryOfVLTree*& 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_SZ++;push_RightMost(t1...);RE;}TE TE VO VLSubTree::push_RightMost(CO VLTree& t0,CO Args&... t1){push_RightMost(t0.m_p_root->m_t);Concatenate(t0);push_RightMost(t1...);RE;}TE TE VO VLSubTree::push_LeftMost(CO Arg& t){auto p = new EntryOfVLTree(t);EntryOfVLTree*& 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_SZ++;RE;}TE VO VLSubTree::pop_RightMost(){assert(m_SZ > 0);EntryOfVLTree* p_rightmost = m_p_root->m_rightmost_node;VLSubTree t{*p_rightmost};t.CutBranches();if(m_SZ == 1){m_p_root->m_leftmost_node = m_p_root;m_p_root->m_rightmost_node = m_p_root;}else{EntryOfVLTree* CO& 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_SZ--;RE;}TE VO VLSubTree::pop_LeftMost(){assert(m_SZ > 0);EntryOfVLTree* p_leftmost = m_p_root->m_leftmost_node;VLSubTree t{*p_leftmost};t.CutBranches();if(m_SZ == 1){m_p_root->m_leftmost_node = m_p_root;m_p_root->m_rightmost_node = m_p_root;}else{EntryOfVLTree* CO& 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_SZ--;RE;}TE VO VLSubTree::pop_Root(){assert(m_SZ == 1);EntryOfVLTree* 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;EntryOfVLTree* p_node = m_p_root->m_leftmost_node;m_SZ = 0;if(p_node != m_p_root){m_SZ++;WH(p_node != p_node->m_right_branch){p_node = p_node->m_right_branch;m_SZ++;}}RE;}TE IN TY VLSubTree::iterator VLSubTree::LeftMostNode()NE{RE IteratorOfVLTree(m_p_root->m_leftmost_node);}TE IN TY VLSubTree::CO_iterator VLSubTree::LeftMostNode()CO NE{RE COIteratorOfVLTree(m_p_root->m_leftmost_node);}TE IN TY VLSubTree::iterator VLSubTree::RightMostNode()NE{RE IteratorOfVLTree(m_p_root->m_rightmost_node);}TE IN TY VLSubTree::CO_iterator VLSubTree::RightMostNode()CO NE{RE COIteratorOfVLTree(m_p_root->m_rightmost_node);}TE TY VLSubTree::iterator VLSubTree::LeftMostLeaf()NE{EntryOfVLTree* p = m_p_root->m_leftmost_node;WH(p != p->m_leftmost_node){p = p->m_leftmost_node;}RE IteratorOfVLTree(p);}TE TY VLSubTree::CO_iterator VLSubTree::LeftMostLeaf()CO NE{CO EntryOfVLTree* p = m_p_root->m_leftmost_node;WH(p != p->m_leftmost_node){p = p->m_leftmost_node;}RE COIteratorOfVLTree(p);}TE TY VLSubTree::iterator VLSubTree::RightMostLeaf()NE{EntryOfVLTree* p = m_p_root->m_rightmost_node;WH(p != p->m_rightmost_node){p = p->m_rightmost_node;}RE IteratorOfVLTree(p);}TE TY VLSubTree::CO_iterator VLSubTree::RightMostLeaf()CO NE{CO EntryOfVLTree* p = m_p_root->m_rightmost_node;WH(p != p->m_rightmost_node){p = p->m_rightmost_node;}RE COIteratorOfVLTree(p);}TE IN TY VLSubTree::iterator VLSubTree::Root()NE{RE IteratorOfVLTree(m_p_root);}TE IN TY VLSubTree::CO_iterator VLSubTree::Root()CO NE{RE COIteratorOfVLTree(m_p_root);}TE TE IN TY VLSubTree::iterator VLSubTree::GetIterator(CO Args&... args){RE Root().Shift(args...);}TE TE IN TY VLSubTree::CO_iterator VLSubTree::GetIterator(CO Args&... args)CO{RE Root().Shift(args...);}TE TE VO VLSubTree::insert(CO TY VLSubTree::iterator& itr,CO Arg& t){assert(CheckContain(itr));EntryOfVLTree* CO& p0 = itr.m_p;EntryOfVLTree* CO& p1 = p0->m_right_branch;auto p = new EntryOfVLTree(t,p0,p1);p1->m_left_branch = p;p0->m_right_branch = p;m_SZ++;RE;}TE TY VLSubTree::iterator VLSubTree::erase(TY VLSubTree::iterator& itr){assert(CheckContain(itr));EntryOfVLTree* CO p = itr.m_p;EntryOfVLTree* CO p0 = p->m_left_branch;EntryOfVLTree* CO p1 = p->m_right_branch;if(! itr.IsLeaf()){VLSubTree 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_SZ--;RE itr;}TE IN CO T& VLSubTree::GetRoot()CO NE{RE m_p_root->m_t;}TE IN T& VLSubTree::RefRoot()NE{RE m_p_root->m_t;}TE IN VO VLSubTree::SetRoot(CO T& t){m_p_root->m_t = t;}TE TE IN CO T& VLSubTree::GetNode(CO Args&... args)CO{RE *(GetIterator(args...));}TE VLSubTree VLSubTree::OP[](CRUI i){assert(i < m_SZ);if(i <= m_SZ / 2){EntryOfVLTree* p = m_p_root->m_leftmost_node;for(uint n = 0;n < i;n++){p = p->m_right_branch;}RE VLSubTree(*p);}EntryOfVLTree* p = m_p_root->m_rightmost_node;for(uint n = m_SZ - 1;n > i;n--){p = p->m_left_branch;}RE VLSubTree(*p);}TE VLSubTree VLSubTree::OP[](TY VLSubTree::iterator& itr){assert(CheckContain(itr));RE VLSubTree(*(itr.m_p));}TE VLTree VLSubTree::OP[](CO TY VLSubTree::CO_iterator& itr)CO{assert(CheckContain(itr));RE VLTree(0,itr.m_p);}TE VLTree VLSubTree::GetBranchCopy(CRUI i)CO{assert(i < m_SZ);if(i <= m_SZ / 2){CO EntryOfVLTree* p = m_p_root->m_leftmost_node;for(uint n = 0;n < i;n++){p = p->m_right_branch;}RE VLTree(0,*p);}CO EntryOfVLTree* p = m_p_root->m_rightmost_node;for(uint n = m_SZ - 1;n > i;n--){p = p->m_left_branch;}RE VLTree(0,*p);}TE VLTree VLSubTree::GetBranchCopy(CO TY VLSubTree::iterator& itr)CO{assert(CheckContain(itr));RE VLTree(0,*(itr.m_p));}TE VLTree VLSubTree::GetBranchCopy(CO TY VLSubTree::CO_iterator& itr)CO{assert(CheckContain(itr));RE VLTree(0,*(itr.m_p));}TE VO VLSubTree::Concatenate(CO VLTree& t){EntryOfVLTree* CO p_rightmost = m_p_root->m_rightmost_node;assert(p_rightmost->m_rightmost_node == p_rightmost);if(m_p_root == p_rightmost){LeafToTree(t);}else{VLSubTree(*p_rightmost).LeafToTree(t);}RE;}TE VO VLSubTree::Concatenate(CO TY VLSubTree::iterator& itr,CO VLTree& t){assert(itr.IsLeaf());EntryOfVLTree* CO p = itr.m_p;if(m_p_root == p){LeafToTree(t);}else{VLSubTree(*p).LeafToTree(t);}RE;}TE VO VLSubTree::Graft(VLSubTree& t){EntryOfVLTree*& 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;}RE;}TE bool VLSubTree::CheckContain(CO iterator& itr)CO NE{auto p0 = itr.m_p;auto p1 = m_p_root->m_leftmost_node;for(uint i = 0;i < m_SZ;i++){if(p0 == p1){RE true;}p1 = p1->m_right_branch;}RE false;}TE bool VLSubTree::CheckContain(CO CO_iterator& itr)CO NE{auto p0 = itr.m_p;auto p1 = m_p_root->m_leftmost_node;for(uint i = 0;i < m_SZ;i++){if(p0 == p1){RE true;}p1 = p1->m_right_branch;}RE false;}TE string VLSubTree::Display()CO{string s = to_string(m_p_root->m_t);s += "(";CO EntryOfVLTree* p = m_p_root->m_leftmost_node;for(uint i = 0;i < m_SZ;i++){if(i > 0){s += ",";}s += VLTree(0,*p).Display();p = p->m_right_branch;}s += ")";RE s;}TE bool OP==(CO VLTree& t1,CO VLTree& t2){if(t1.GetRoot()!= t2.GetRoot()){RE false;}if(t1.IsLeaf()){RE t2.IsLeaf();}if(t2.IsLeaf()){RE false;}auto itr1 = t1.LeftMostNode();auto itr2 = t2.LeftMostNode();WH(itr1.IsValid()&& itr2.IsValid()){if(t1.GetBranchCopy(*itr1)!= t2.GetBranchCopy(*itr2)){RE false;}itr1++;itr2++;}RE !(itr1.IsValid()|| itr2.IsValid());}TE IN bool OP!=(CO VLTree& t1,CO VLTree& t2){RE !(t1 == t2);} TE CL EntryOfLinkedVE{PU:T m_t;uint m_prev_entry;uint m_next_entry;IN EntryOfLinkedVE();IN EntryOfLinkedVE(CRUI prev_entry,CRUI next_entry);IN EntryOfLinkedVE(EntryOfLinkedVE&& e);}; TE IN EntryOfLinkedVE::EntryOfLinkedVE(): m_t(),m_prev_entry(0),m_next_entry(0){}TE IN EntryOfLinkedVE::EntryOfLinkedVE(CRUI prev_entry,CRUI next_entry): m_t(),m_prev_entry(prev_entry),m_next_entry(next_entry){}TE IN EntryOfLinkedVE::EntryOfLinkedVE(EntryOfLinkedVE&& e): m_t(MO(e.m_t)),m_prev_entry(MO(e.m_prev_entry)),m_next_entry(MO(e.m_next_entry)){} TE CL LinkedVE; TE CL IteratorOfLinkedVE{PU:LinkedVE* m_p;uint m_i;IN IteratorOfLinkedVE(LinkedVE* CO& p,CRUI i)NE;IN IteratorOfLinkedVE(CO IteratorOfLinkedVE& itr)NE;IN T& OP*()CO;IN T* OP->()CO;IteratorOfLinkedVE& OP=(CO IteratorOfLinkedVE& itr)NE;IN VO OP++(int);IN VO OP--(int);IN CO LinkedVE& GetLinkedVE()CO NE;IN LinkedVE& RefLinkedVE()NE;IN CRUI GetIndex()CO NE;IN CRUI RefIndex()NE;}; TE CL COIteratorOfLinkedVE{PU:CO LinkedVE* m_p;uint m_i;IN COIteratorOfLinkedVE(CO LinkedVE* CO& p,CRUI i)NE;IN COIteratorOfLinkedVE(CO COIteratorOfLinkedVE& itr)NE;IN COIteratorOfLinkedVE(CO IteratorOfLinkedVE& itr)NE;IN CO T& OP*()CO;IN CO T* OP->()CO;COIteratorOfLinkedVE& OP=(CO COIteratorOfLinkedVE& itr)NE;COIteratorOfLinkedVE& OP=(CO IteratorOfLinkedVE& itr)NE;IN VO OP++(int);IN VO OP--(int);IN CO LinkedVE& GetLinkedVE()CO NE;IN CRUI GetIndex()CO NE;IN CRUI RefIndex()NE;ST IN bool Equal(CO IteratorOfLinkedVE&,CO IteratorOfLinkedVE&)NE;ST IN bool Equal(CO COIteratorOfLinkedVE&,CO IteratorOfLinkedVE&)NE;ST IN bool Equal(CO IteratorOfLinkedVE&,CO COIteratorOfLinkedVE&)NE;ST IN bool Equal(CO COIteratorOfLinkedVE&,CO COIteratorOfLinkedVE&)NE;}; TE IN IteratorOfLinkedVE::IteratorOfLinkedVE(LinkedVE* CO& p,CRUI i)NE:m_p(p),m_i(i){}TE IN IteratorOfLinkedVE::IteratorOfLinkedVE(CO IteratorOfLinkedVE& itr)NE:m_p(itr.m_p),m_i(itr.m_i){}TE IN T& IteratorOfLinkedVE::OP*()CO{RE(*m_p)[m_i];}TE IN T* IteratorOfLinkedVE::OP->()CO{RE &((*m_p)[m_i]);}TE IN IteratorOfLinkedVE& IteratorOfLinkedVE::OP=(CO IteratorOfLinkedVE& itr)NE{m_p = itr.m_p;m_i = itr.m_i;RE *TH;}TE IN VO IteratorOfLinkedVE::OP++(int){m_i = m_p->m_entry[m_i].m_next_entry;}TE IN VO IteratorOfLinkedVE::OP--(int){m_i = m_p->m_entry[m_i].m_prev_entry;}TE IN CO LinkedVE& IteratorOfLinkedVE::GetLinkedVE()CO NE{RE *m_p;}TE IN LinkedVE& IteratorOfLinkedVE::RefLinkedVE()NE{RE *m_p;}TE IN CRUI IteratorOfLinkedVE::GetIndex()CO NE{RE m_i;}TE IN CRUI IteratorOfLinkedVE::RefIndex()NE{RE m_i;}TE IN COIteratorOfLinkedVE::COIteratorOfLinkedVE(CO LinkedVE* CO& p,CRUI i)NE:m_p(p),m_i(i){}TE IN COIteratorOfLinkedVE::COIteratorOfLinkedVE(CO COIteratorOfLinkedVE& itr)NE:m_p(itr.m_p),m_i(itr.m_i){}TE IN COIteratorOfLinkedVE::COIteratorOfLinkedVE(CO IteratorOfLinkedVE& itr)NE:m_p(itr.m_p),m_i(itr.m_i){}TE IN CO T& COIteratorOfLinkedVE::OP*()CO{RE(*m_p)[m_i];}TE IN CO T* COIteratorOfLinkedVE::OP->()CO{RE &((*m_p)[m_i]);}TE COIteratorOfLinkedVE& COIteratorOfLinkedVE::OP=(CO COIteratorOfLinkedVE& itr)NE{m_p = itr.m_p;m_i = itr.m_i;RE *TH;}TE COIteratorOfLinkedVE& COIteratorOfLinkedVE::OP=(CO IteratorOfLinkedVE& itr)NE{m_p = itr.m_p;m_i = itr.m_i;RE *TH;}TE IN VO COIteratorOfLinkedVE::OP++(int){m_i = m_p->m_entry[m_i].m_next_entry;}TE IN VO COIteratorOfLinkedVE::OP--(int){m_i = m_p->m_entry[m_i].m_prev_entry;}TE IN CO LinkedVE& COIteratorOfLinkedVE::GetLinkedVE()CO NE{RE *m_p;}TE IN CRUI COIteratorOfLinkedVE::GetIndex()CO NE{RE m_i;}TE IN CRUI COIteratorOfLinkedVE::RefIndex()NE{RE m_i;}TE IN bool COIteratorOfLinkedVE::Equal(CO IteratorOfLinkedVE& itr0,CO IteratorOfLinkedVE& itr1)NE{RE itr0.m_p == itr1.m_p && itr0.m_i == itr1.m_i;}TE IN bool COIteratorOfLinkedVE::Equal(CO COIteratorOfLinkedVE& itr0,CO IteratorOfLinkedVE& itr1)NE{RE itr0.m_p == itr1.m_p && itr0.m_i == itr1.m_i;}TE IN bool COIteratorOfLinkedVE::Equal(CO IteratorOfLinkedVE& itr0,CO COIteratorOfLinkedVE& itr1)NE{RE itr0.m_p == itr1.m_p && itr0.m_i == itr1.m_i;}TE IN bool COIteratorOfLinkedVE::Equal(CO COIteratorOfLinkedVE& itr0,CO COIteratorOfLinkedVE& itr1)NE{RE itr0.m_p == itr1.m_p && itr0.m_i == itr1.m_i;}TE IN bool OP==(CO IteratorOfLinkedVE& itr0,CO IteratorOfLinkedVE& itr1)NE{RE COIteratorOfLinkedVE::Equal(itr0,itr1);}TE IN bool OP!=(CO IteratorOfLinkedVE& itr0,CO IteratorOfLinkedVE& itr1)NE{RE !(itr0 == itr1);}TE IN bool OP==(CO COIteratorOfLinkedVE& itr0,CO IteratorOfLinkedVE& itr1)NE{RE COIteratorOfLinkedVE::Equal(itr0,itr1);}TE IN bool OP!=(CO COIteratorOfLinkedVE& itr0,CO IteratorOfLinkedVE& itr1)NE{RE !(itr0 == itr1);}TE IN bool OP==(CO IteratorOfLinkedVE& itr0,CO COIteratorOfLinkedVE& itr1)NE{RE COIteratorOfLinkedVE::Equal(itr0,itr1);}TE IN bool OP!=(CO IteratorOfLinkedVE& itr0,CO COIteratorOfLinkedVE& itr1)NE{RE !(itr0 == itr1);}TE IN bool OP==(CO COIteratorOfLinkedVE& itr0,CO COIteratorOfLinkedVE& itr1)NE{RE COIteratorOfLinkedVE::Equal(itr0,itr1);}TE IN bool OP!=(CO COIteratorOfLinkedVE& itr0,CO COIteratorOfLinkedVE& itr1)NE{RE !(itr0 == itr1);} TE CL LinkedVE{PU:VE > m_entry;uint m_front_linked_entry;uint m_back_linked_entry;uint m_SZ_of_VE;uint m_SZ_of_link;IN LinkedVE();IN LinkedVE(CRUI max_SZ);IN CO T& OP[](CRUI i)CO;IN T& OP[](CRUI i);uint GetLinkedEntry(CRUI i)CO;IN CRUI GetFrontLinkedEntryIndex()CO NE;IN CRUI GetBackLinkedEntryIndex()CO NE;IN CRUI GetSZOfVE()CO NE;IN CRUI GetSZOfLink()CO NE;IN bool EmptyVE()CO NE;IN bool EmptyLink()CO NE;IN VO push_back();TE VO push_back(CO U& u);TE IN VO push_back(CO U& u,CO ARGS&... args);IN VO SetPreviousLink(CRUI i,CRUI j);IN VO SetNexttLink(CRUI i,CRUI j);IN CRUI GetPreviousLinkIndex(CRUI i)CO;IN CRUI GetNexttLinkIndex(CRUI i)CO;CRUI DeLink(CRUI i);VO ReLink(CRUI i);US iterator = IteratorOfLinkedVE;US CO_iterator = COIteratorOfLinkedVE;IN iterator GetIterator(CRUI i)NE;IN CO_iterator GetIterator(CRUI i)CO NE;IN iterator BE()NE;IN CO_iterator BE()CO NE;IN iterator EN()NE;IN CO_iterator EN()CO NE;iterator erase(iterator& itr);IN EntryOfLinkedVE& push_back_Body_0();IN VO push_back_Body_1(EntryOfLinkedVE& e);}; TE IN LinkedVE::LinkedVE(): m_entry(1),m_front_linked_entry(0),m_back_linked_entry(0),m_SZ_of_VE(0),m_SZ_of_link(0){}TE IN LinkedVE::LinkedVE(CRUI max_SZ): m_entry(),m_front_linked_entry(0),m_back_linked_entry(0),m_SZ_of_VE(0),m_SZ_of_link(0){m_entry.reserve(max_SZ + 1);m_entry.push_back(EntryOfLinkedVE());}TE IN CO T& LinkedVE::OP[](CRUI i)CO{RE m_entry[i].m_t;}TE IN T& LinkedVE::OP[](CRUI i){RE m_entry[i].m_t;}TE uint LinkedVE::GetLinkedEntry(CRUI i)CO{uint linked_entry = m_front_linked_entry;for(uint j = 0;j < i;j++){linked_entry = m_entry[linked_entry].m_next_entry;}RE linked_entry;}TE IN CRUI LinkedVE::GetFrontLinkedEntryIndex()CO NE{RE m_front_linked_entry;}TE IN CRUI LinkedVE::GetBackLinkedEntryIndex()CO NE{RE m_back_linked_entry;}TE IN CRUI LinkedVE::GetSZOfVE()CO NE{RE m_SZ_of_VE;}TE IN CRUI LinkedVE::GetSZOfLink()CO NE{RE m_SZ_of_link;}TE IN bool LinkedVE::EmptyVE()CO NE{RE m_SZ_of_VE == 0;}TE IN bool LinkedVE::EmptyLink()CO NE{RE m_SZ_of_link == 0;}TE IN VO LinkedVE::push_back(){}TE TE VO LinkedVE::push_back(CO U& u){EntryOfLinkedVE& e = push_back_Body_0();e.m_t = u;push_back_Body_1(e);RE;}TE TE IN VO LinkedVE::push_back(CO U& u,CO ARGS&... args){push_back(u);push_back(args...);}TE IN EntryOfLinkedVE& LinkedVE::push_back_Body_0(){m_entry.push_back(EntryOfLinkedVE(m_SZ_of_VE,m_front_linked_entry));RE m_entry[m_SZ_of_VE];}TE IN VO LinkedVE::push_back_Body_1(EntryOfLinkedVE& e){e.m_next_entry = m_SZ_of_VE + 1;m_entry[m_front_linked_entry].m_prev_entry = m_SZ_of_VE + 1;m_back_linked_entry = m_SZ_of_VE;m_SZ_of_VE++;m_SZ_of_link++;}TE IN VO LinkedVE::SetPreviousLink(CRUI i,CRUI j){m_entry[i].m_prev_entry = j;}TE IN VO LinkedVE::SetNexttLink(CRUI i,CRUI j){m_entry[i].m_next_entry = j;}TE IN CRUI LinkedVE::GetPreviousLinkIndex(CRUI i)CO{RE m_entry[i].m_prev_entry;}TE IN CRUI LinkedVE::GetNexttLinkIndex(CRUI i)CO{RE m_entry[i].m_next_entry;}TE CRUI LinkedVE::DeLink(CRUI i){CO EntryOfLinkedVE& 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_SZ_of_link--;RE e.m_next_entry;}TE VO LinkedVE::ReLink(CRUI i){EntryOfLinkedVE& current_entry = m_entry[i];if(m_SZ_of_link == 0){EntryOfLinkedVE& EN_entry = m_entry[m_SZ_of_VE];EN_entry.m_prev_entry = EN_entry.m_next_entry = i;current_entry.m_prev_entry = current_entry.m_next_entry = m_SZ_of_VE;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_SZ_of_VE;}else{prev = m_front_linked_entry;}if(m_back_linked_entry < i){m_back_linked_entry = i;}prev = m_entry[prev].m_next_entry;WH(prev < i){prev = m_entry[prev].m_next_entry;}CO uint next = prev;EntryOfLinkedVE& next_entry = m_entry[next];prev = next_entry.m_prev_entry;EntryOfLinkedVE& 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_SZ_of_link++;RE;}TE IN TY LinkedVE::iterator LinkedVE::GetIterator(CRUI i)NE{RE TY LinkedVE::iterator(TH,i);}TE IN TY LinkedVE::CO_iterator LinkedVE::GetIterator(CRUI i)CO NE{RE TY LinkedVE::CO_iterator(TH,i);}TE IN TY LinkedVE::iterator LinkedVE::BE()NE{RE TY LinkedVE::iterator(TH,m_front_linked_entry);}TE IN TY LinkedVE::CO_iterator LinkedVE::BE()CO NE{RE TY LinkedVE::CO_iterator(TH,m_front_linked_entry);}TE IN TY LinkedVE::iterator LinkedVE::EN()NE{RE TY LinkedVE::iterator(TH,m_SZ_of_VE);}TE IN TY LinkedVE::CO_iterator LinkedVE::EN()CO NE{RE TY LinkedVE::CO_iterator(TH,m_SZ_of_VE);}TE TY LinkedVE::iterator LinkedVE::erase(TY LinkedVE::iterator& itr){RE TY LinkedVE::iterator(TH,DeLink(itr.m_i));} TE CL EntryOfUnionFindForest{PU:VLSubTree m_node;uint m_pred_node;uint m_root;uint m_depth;IN EntryOfUnionFindForest();IN EntryOfUnionFindForest(CO T& t,CRUI num);IN EntryOfUnionFindForest(EntryOfUnionFindForest&& e);};TE IN EntryOfUnionFindForest::EntryOfUnionFindForest(): m_node(),m_pred_node(0),m_root(0),m_depth(0){}TE IN EntryOfUnionFindForest::EntryOfUnionFindForest(CO T& t,CRUI num): m_node(),m_pred_node(num),m_root(num),m_depth(0){m_node.SetRoot(t);}TE IN EntryOfUnionFindForest::EntryOfUnionFindForest(EntryOfUnionFindForest&& e): m_node(),m_pred_node(MO(e.m_pred_node)),m_root(MO(e.m_root)),m_depth(MO(e.m_depth)){m_node.SetRoot(MO(e.m_node.m_p_root->m_t));}TE CL UnionFindForest :public LinkedVE >{PU:IN UnionFindForest(CRUI max_SZ);IN CO VLSubTree& GetSubTree(CRUI num)CO;IN CRUI GetPredecessorNode(CRUI num)CO;CRUI GetRootOfNode(CRUI num);uint GetRoot(CRUI num)CO;IN CO T& OP[](CRUI num)CO;IN T& OP[](CRUI num);IN CRUI GetSZOfNode()CO NE;IN CRUI GetSZOfRoot()CO NE;IN VO push_RightMost();VO push_RightMost(CO T& t);TE IN VO push_RightMost(CO T& t,CO ARGS&... args);IN VO push_back()= delete;TE VO push_back(CO U& u)= delete;TE IN VO push_back(CO U& u,CO ARGS&... args)= delete;IN VO SetPreviousLink(CRUI i,CRUI j)= delete;IN VO SetNexttLink(CRUI i,CRUI j)= delete;IN CRUI GetPreviousLinkIndex(CRUI i)CO = delete;IN CRUI GetNexttLinkIndex(CRUI i)CO = delete;CRUI DeLink(CRUI i)= delete;VO ReLink(CRUI i)= delete;VO Graft(CRUI num0,CRUI num1);}; TE IN UnionFindForest::UnionFindForest(CRUI max_SZ): LinkedVE >(max_SZ){}TE IN CO VLSubTree& UnionFindForest::GetSubTree(CRUI num)CO{RE LinkedVE >::OP[](num).m_node;}TE IN CRUI UnionFindForest::GetPredecessorNode(CRUI num)CO{RE LinkedVE >::OP[](num).m_pred_node;}TE CRUI UnionFindForest::GetRootOfNode(CRUI num){uint& root = LinkedVE >::OP[](num).m_root;if(root != LinkedVE >::OP[](root).m_root){root = GetRootOfNode(root);}RE root;}TE uint UnionFindForest::GetRoot(CRUI num)CO{auto itr = LinkedVE >::BE();for(uint i = 0;i < num;i++){itr++;}RE itr.GetIndex();}TE IN CO T& UnionFindForest::OP[](CRUI num)CO{RE LinkedVE >::OP[](num).m_node.GetRoot();}TE IN T& UnionFindForest::OP[](CRUI num){RE LinkedVE >::OP[](num).m_node.RefRoot();}TE IN CRUI UnionFindForest::GetSZOfNode()CO NE{RE LinkedVE >::GetSZOfVE();}TE IN CRUI UnionFindForest::GetSZOfRoot()CO NE{RE LinkedVE >::GetSZOfLink();}TE IN VO UnionFindForest::push_RightMost(){}TE VO UnionFindForest::push_RightMost(CO T& t){EntryOfLinkedVE >& e = LinkedVE >::push_back_Body_0();e.m_t.m_node.SetRoot(t);e.m_t.m_pred_node = e.m_t.m_root = LinkedVE >::m_SZ_of_VE;LinkedVE >::push_back_Body_1(e);RE;}TE TE IN VO UnionFindForest::push_RightMost(CO T& t,CO ARGS&... args){push_RightMost(t);push_RightMost(args...);}TE VO UnionFindForest::Graft(CRUI num0,CRUI num1){CRUI e0_root_index = GetRootOfNode(num0);CRUI e1_root_index = GetRootOfNode(num1);if(e0_root_index == e1_root_index){RE;}EntryOfUnionFindForest& e0_root = LinkedVE >::OP[](e0_root_index);EntryOfUnionFindForest& e1_root = LinkedVE >::OP[](e1_root_index);CO uint i0 =(e0_root.m_depth < e1_root.m_depth?0:1);CO uint i1 = 1 - i0;EntryOfUnionFindForest* CO p_e_root[2] ={&e0_root,&e1_root};EntryOfUnionFindForest& root_0 = *(p_e_root[i0]);EntryOfUnionFindForest& 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);LinkedVE >::DeLink(root_0.m_root);root_0.m_root = root_0.m_pred_node = root_1.m_root;RE;} int main() { UNTIE; CEXPR( int , bound , 200000 ); CIN_ASSERT( W , 1 , bound ); CIN_ASSERT( H , 1 , bound / W ); UnionFindForest uf{ W }; REPEAT( W ){ uf.push_RightMost( -1 ); } string num[10] = {"0","1","2","3","4","5","6","7","8","9"}; string hatena = "?"; bool contradict{}; CEXPR( ll , P , 998244353 ); REPEAT( H ){ if( contradict ){ COUT( 0 ); } else { CIN( string , Qi ); map coord{}; FOR( j , 0 , W ){ string Qij = Qi.substr( j , 1 ); if( Qij != hatena ){ bool found{}; FOR( n , 0 , 10 ){ if( Qij == num[n] ){ int& ufj = uf[uf.GetRootOfNode( j )]; if( ufj == -1 ){ ufj = n; } else { if( ufj != n ){ contradict = true; } } found = true; break; } } if( !found ){ if( coord.count( Qij ) == 0 ){ coord[Qij] = uf.GetRootOfNode( j ); } else { int root_j = uf.GetRootOfNode( j ); int& coord_ij = coord[Qij]; int& ufj = uf[root_j]; int& ufk = uf[coord_ij]; if( ufj == -1 ){ ufj = ufk; } else { if( ufk == -1 ){ ufk = ufj; } else { if( ufk != ufj ){ contradict = true; } } } if( !contradict && root_j != coord_ij ){ uf.Graft( root_j , coord_ij ); coord_ij = uf.GetRootOfNode( root_j ); } } } } } if( contradict ){ COUT( 0 ); } else { int count = 0; FOR_ITR( uf , itr , end ){ int& ufj = uf[itr.GetIndex()]; if( ufj == -1 ){ count++; } } POWER_MOD( answer , ll( 10 ) , count , P ); COUT( answer ); } } } QUIT; }