//==================================================================================================
// Name        : ArifuretaFromCommonPlaceToWorldsStrongest.cpp
// Author      : lotus.eater086
// Copyright   : If you're reading this then this warning is for you. Every word you read of this 
//               useless fine print is another second of your life. Don't you've other things to do?
//               Is your life so empty that you honestly can't think of a better way to spend these
//               moments ? Or are you so impressed with authority that you give respect and 
//               credence to all who claim it ? Do you read everything you're supposed to read ? Do
//               you think everything you're supposed to think ? Buy what you're told you should 
//               want ? Get out of your apartment . Meet a member of the opposite sex. Stop the 
//               excessive shopping and self-improvement . Quit your boring job.
//               Start a fight. Prove you're alive. If you don't claim your humanity you'll become a
//               statistic. You've been warned !

// Description : 
// Date        : 2019-10-13
// Time        : 18:01:36
// Directory   : C:\Users\Lenovo\cpPractise\deliberatePractise\code_folder\.vscode
// FilePath    : C:\Users\Lenovo\cpPractise\deliberatePractise\code_folder\.vscode\ArifuretaFromCommonPlaceToWorldsStrongest.cpp
//==================================================================================================
    

#include <bits/stdc++.h>
#define LL long long
#define endl "\n"

using namespace std ;
    
//
template < typename T >

inline T read( T &x )
{

    x = 0 ;

    int f = 0 ;

    char ch = getchar() ;

    while( ch < '0' || ch > '9' )  {

        f |= ( ch == '-' ) , ch = getchar() ;

    }

    while( ch >= '0' && ch <= '9' )  {

        x = ( x << 1 ) + ( x << 3 ) + ch - '0' , ch = getchar() ;

    }

    return x = f ? -x:x ;

}
//

void bubble_sort( vector<pair<int,pair<char,int>>> &v , int n )
{

    for( int i = 0 ; i < n ; i++ )  {

        for( int j = n-1 ; j >= i+1 ; j-- )  {

            if( v[j].first < v[j-1].first )  {

                swap( v[j] , v[j-1] ) ;    

            }

        }

    }

}

void selection_sort( vector<pair<int,pair<char,int>>> &v , int n )  
{

    for( int i = 0 ; i < n ; i++ )  {

        int mini = i ;

        for( int j = i ; j < n ; j++ )  {

            if( v[j].first < v[mini].first )  {

                mini = j ; 

            }

        }

        swap( v[i] , v[mini] ) ;  

    }

}

bool stability_check( vector<pair<int,pair<char,int>>> v , int n )
{

    bool flag = true ;

    for( int i = 0 ; i < n-1 ; i++ )  {

        if( v[i].first == v[i+1].first && v[i].second.second > v[i+1].second.second )  {

            flag = false ;

            break ;

        }

    }

    return flag ;  

}

void print_vector( vector<pair<int,pair<char,int>>> v , int n )
{

    cout << v[0].second.first << v[0].first ;

    for( int i = 1 ; i < n ; i++ )  {

        cout << " " << v[i].second.first << v[i].first ;   

    }

}

void solve( void )
{

    int n ;

    read( n ) ;

    vector<pair<int,pair<char,int>>> v( n ) , temp( v ) ;  // value , ( letter , order )

    for( int i = 0 ; i < n ; i++ )  {

        string s ;

        cin >> s ;

        //cout << s << endl ;

        char letter = s[0] ;      //    cout << letter << endl ;

        int value = s[1] - '0' ;     //   cout << value << endl ; 

        v[i].first = value ;     //   cout << v[i].first << endl ; 

        v[i].second.first = letter ;

        v[i].second.second = i ;  

      //  cout << v[i].first << " " << v[i].second.first << " " << v[i].second.second << endl ; 

    }

    temp.assign( v.begin() , v.end() ) ;  

    bubble_sort( v , n ) ;

    print_vector( v , n ) ;  

    cout << "\nStable\n" ;

    selection_sort( temp , n ) ;

    print_vector( temp , n ) ;  

    if( stability_check( temp , n ) )  {

        cout << "\nStable\n" ;

    }

    else  {

        cout << "\nNot stable\n" ;

    }



}

int main( void )

{

    //ios_base::sync_with_stdio( false ) ;  cin.tie( NULL ) ;  cout.tie( NULL ) ;

   

    if( 0 )  {

        int t = 100 ;

        for( int i = 1 ; i <= t ; i++ )  solve() ;

    }

    else  {

        solve() ;

    }

   

    return 0 ;

}



Measured memory_bytes: 3132