using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace CsharpSpiral {
    partial class Program {
        //https://qiita.com/NotFounds/items/7b166af69a6f52a332de
        static void Main(string[] args) {
            var sw = new StreamWriter( Console.OpenStandardOutput() ) { AutoFlush = false };
            Console.SetOut( sw );
            new Program().Solve( new ConsoleInput( Console.In, ' ' ) );
            Console.Out.Flush();
        }
        struct Card: IComparable<Card> {
            char suit { get; set; }
            int value { get; set; }
            public Card(string info) {
                suit = info[0];
                value = int.Parse( info.Substring( 1 ) );
            }
            public int CompareTo(Card y) => value.CompareTo( y.value );
            public override string ToString() => suit.ToString() + value.ToString();
        }
        public void Solve(ConsoleInput cin) {
            var N = cin.ReadInt;
            var D = cin.ReadStrArray( N ).Select( s => new Card( s ) ).ToArray();
            var C = new Card[N];
            Array.Copy( D, C, N );
            BubbleSort( C );
            Console.WriteLine( C.Join() );
            Console.WriteLine( isStable( D, C, N )?"Stable":"Not stable" );
            Array.Copy( D, C, N );
            SelectionSort( C );
            Console.WriteLine( C.Join() );
            Console.WriteLine( isStable( D, C, N ) ? "Stable" : "Not stable" );

        }
        public void BubbleSort<T>(T[] A) where T : IComparable<T> {
            var N = A.Length;
            var flag = true;
            while (flag) {
                flag = false;
                for (int i = N - 2; i >= 0; i--) {
                    if (A[i].CompareTo( A[i + 1] ) > 0) {
                        A.Swap( i, i + 1 );
                        flag = true;
                    }
                }
            }
        }
        public void SelectionSort<T>(T[] A) where T : IComparable<T> {
            var N = A.Length;
            for (int i = 0; i < N; i++) {
                var mi = i;
                for (int j = i + 1; j < N; j++) {
                    if (A[j].CompareTo(A[mi])<0) {
                        mi = j;
                    }
                }
                if (i != mi) 
                    A.Swap( i, mi );
            }
        }   

        public bool isStable<T>(T[] src, T[] dst, int N) where T: IComparable<T> {
            int[] map = new int[N];
            for (int i = 0; i < N; i++) {
                map[i] = Array.IndexOf( dst, src[i] );
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (src[i].CompareTo( src[j] ) == 0) {
                        if (i<j && map[i] > map[j]) return false;
                    }
                }
            }
            return true;
        }
    }

    static class ExtendClass {
        public static void Swap<T>(this T[] X, int i, int j) {
            T tmp = X[i];
            X[i] = X[j];
            X[j] = tmp;
        }
        public static string Join<T> (this T[] X, string separator = " ") => string.Join( separator, X);
    }

    class ConsoleInput {
        private readonly TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(TextReader stream, char separator = ' ') {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read {
            get {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split( _separator );
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue( tmp[i] );
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse( Read ); } }
        public long ReadLong { get { return long.Parse( Read ); } }
        public double ReadDouble { get { return double.Parse( Read ); } }
        public string[] ReadStrArray(long N) {
            var ret = new string[N];
            for (long i = 0; i < N; ++i)
                ret[i] = Read;
            return ret;
        }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}



Measured memory_bytes: 18748