using System.Collections.Generic;
using System.Linq;
using static System.Console;
namespace StableSort
{
    public static class Program
    {
        public static void Main(string[] args)
        {
            var n = int.Parse(ReadLine());
            var input = ReadLine().Trim().Split(' ');
            var def = new Card[n];
            var cardsBubble = new Card[n];
            var cardsSelection = new Card[n];

            for (var i = 0; i < cardsBubble.Length; i++)
            {
                // Initialize
                cardsBubble[i] = new Card {Id = int.Parse(input[i].Substring(1)), Suit = input[i].Substring(0, 1)};
                cardsSelection[i] = new Card {Id = int.Parse(input[i].Substring(1)), Suit = input[i].Substring(0, 1)};
                def[i] = new Card {Id = int.Parse(input[i].Substring(1)), Suit = input[i].Substring(0, 1)};
            }
            
            BubbleSort(cardsBubble, n);
            WritePartial(cardsBubble);
            WriteLine(IsStable(def, cardsBubble) ? "Stable" : "Not stable");
            
            SelectionSort(cardsSelection,n);
            WritePartial(cardsSelection);
            WriteLine(IsStable(def, cardsSelection) ? "Stable" : "Not stable");
        }

        private static bool IsStable(IReadOnlyList<Card> input, IReadOnlyList<Card> sorted)
        {
            for (var i = 0; i < input.Count; i++)
            {
                for (var j = i + 1; j < input.Count; j++)
                {
                    for (var a = 0; a < input.Count; a++)
                    {
                        for (var b = a + 1; b < input.Count; b++)
                        {
                            if (input[i].Id == input[j].Id && input[i].Kind == sorted[b].Kind && input[j].Kind == sorted[a].Kind)
                                return false;
                        }
                    }
                }
            }
            return true;
        }

        private static void WritePartial(IEnumerable<Card> card)
        {
            WriteLine(card.Select(c => c.Kind).Aggregate((word, next) => $"{word} {next}"));
        }

        private static void BubbleSort(Card[] cards, int n)
        {
            for (var i = 0; i < n; i++)
            {
                for (var j = n - 1; j > i; j--)
                {
                    if (cards[j].Id < cards[j - 1].Id)
                    {
                        // Swap
                        var tmp = cards[j];
                        cards[j] = cards[j - 1];
                        cards[j - 1] = tmp;
                    }
                }
            }
        }

        private static void SelectionSort(Card[] cards, int n)
        {
            
            for (var i = 0; i < n; i++)
            {
                var minj = i;
                for (var j = i; j < n; j++)
                {
                    // search minimum
                    if (cards[j].Id < cards[minj].Id) minj = j;
                }

                var tmp = cards[i];
                cards[i] = cards[minj];
                cards[minj] = tmp;
            }
        }        
        
    }

    public class Card
    {
        public string Suit { private get; set; }
        public int Id { get; set; }
        public string Kind => $"{Suit}{Id}";
    }
}


Measured memory_bytes: 22488