using System;
using System.Collections.Generic;
using System.Linq;

namespace ALDS_1_2_C
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var v = Console.ReadLine();
            var babbleOriginalList = v.Split(' ').Select(s => new Card(s[0],s[1]-'0')).ToList();
            var selectionOriginalList = v.Split(' ').Select(s => new Card(s[0], s[1] - '0')).ToList();
            var babbleSortList = BabbleSort(babbleOriginalList, n);
            OutputList(babbleSortList);
            if (IsStable(babbleOriginalList,babbleSortList))
            {
                Console.WriteLine("Stable");
            }
            else
            {
                Console.WriteLine("Not stable");
            }
            var selectionSortList = SelectionSort(selectionOriginalList, n);
            OutputList(selectionSortList);
            if (IsStable(selectionOriginalList, babbleSortList))
            {
                Console.WriteLine("Stable");
            }
            else
            {
                Console.WriteLine("Not stable");
            }
        }

        public static List<Card> BabbleSort(List<Card>CardList,int n)
        {
            for(int i=0; i<n-1; i++)
            {
                for(int j=n-1; j>i; j--)
                {
                    if(CardList[j-1].value > CardList[j].value)
                    {
                        Card temp = CardList[j-1];
                        CardList[j-1] = CardList[j];
                        CardList[j] = temp;
                    }
                }
            }
            return CardList;
        }

        public static List<Card> SelectionSort(List<Card>CardList,int n)
        {
            for(int i=0; i<n-1; i++)
            {
                int minj = i;
                for(int j=i+1; j<n; j++)
                {
                    if(CardList[minj].value > CardList[j].value)
                    {
                        minj = j;
                    }
                }
                Card temp = CardList[i];
                CardList[i] = CardList[minj];
                CardList[minj] = temp;
            }
            return CardList;
        }

        public static void OutputList(List<Card> targetArray)
        {
            for (int i = 0; i < targetArray.Count; i++)
            {
                if (i == targetArray.Count - 1)
                {
                    Console.WriteLine(targetArray[i].suit.ToString() + targetArray[i].value);
                }
                else
                {
                    Console.Write(targetArray[i].suit.ToString() + targetArray[i].value);
                    Console.Write(' ');
                }
            }
            return;
        }

        public static bool IsStable(List<Card>inputArray,List<Card>outputArray)
        {
            bool isStable = true;
            var checkSuitList = inputArray.Select(n => n.value).Distinct().ToList();
            for(int i = 0; i < checkSuitList.Count(); i++)
            {
                var checkInputList = inputArray.Where(n => n.value == checkSuitList[i]).Select(n => n.suit).ToList();
                var checkOutputList = outputArray.Where(n => n.value == checkSuitList[i]).Select(n => n.suit).ToList();
                if (!checkInputList.SequenceEqual(checkOutputList))
                {
                    isStable = false;
                    break;
                }
            }
            return isStable;
        }
    }

    public class Card
    {
        public char suit { get; set; }
        public int value { get; set; }

        public Card(char suit, int value)
        {
            this.suit = suit;
            this.value = value;
        }
    }

}



Measured memory_bytes: 20504