using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace StableSort
{
    class Program
    {
        private static bool isStableSelection = true;

        static void Main(string[] args)
        {
            int intLength = int.Parse(Console.ReadLine());
            string[] aryIn = Console.ReadLine().Split(' ');
            Card[] aryCards = aryIn.Select(s => { return new Card(s); }).ToArray();

            Card[] aryBubble = (Card[])aryCards.Clone();
            Card[] arySelection = (Card[])aryCards.Clone();

            //バブルソート実行
            for (int i = 0; i < aryBubble.Length; i++)
            {
                aryBubble = Program.BubbleSort(aryBubble, i);
            }
            Console.WriteLine(string.Join(" ", aryBubble.Select(s => s.ToString()).ToArray()));
            Console.WriteLine("Stable");

            //選択ソート実行
            for (int i = 0; i < arySelection.Length; i++)
            {
                arySelection = Program.SelectionSort(arySelection, i);
            }
            Console.WriteLine(string.Join(" ", arySelection.Select(s => s.ToString()).ToArray()));
            if (Program.isStableSelection)
            {
                Console.WriteLine("Stable");
            }
            else
            {
                Console.WriteLine("Not stable");
            }
            Console.ReadLine();
        }

        /// <summary>
        /// index-1番目の要素までソートしているとみなして、index番目のソートを行う
        /// </summary>
        /// <param name="cards"></param>
        /// <param name="index"></param>
        /// <returns></returns>
        static Card[] BubbleSort(Card[] cards, int index)
        {
            for (int i = cards.Length - 1; i > index; i--)
            {
                if (cards[i-1].isBiggerThan(cards[i]))
                {
                    Card tmp = cards[i - 1];
                    cards[i - 1] = cards[i];
                    cards[i] = tmp;
                }
            }
            return cards;
        }

        /// <summary>
        /// index-1番目の要素までソートしているとみなして、index番目のソートを行う
        /// </summary>
        /// <param name="cards"></param>
        /// <param name="index"></param>
        /// <returns></returns>
        static Card[] SelectionSort(Card[] cards, int index)
        {
            //最小値のインデックス
            int minIndex = index;

            //
            bool isSameNumExists = false;

            for (int i = index + 1; i < cards.Length; i++)
            {
                if (cards[minIndex].intNumber == cards[i].intNumber && cards[minIndex].strSuit != cards[i].strSuit)
                {
                    isSameNumExists = true;
                }
                
                if (cards[minIndex].isBiggerThan(cards[i]))
                {
                    minIndex = i;
                }
            }

            if (minIndex != index)
            {
                Card tmp = cards[minIndex];
                cards[minIndex] = cards[index];
                cards[index] = tmp;

                if (isSameNumExists)
                {
                    Program.isStableSelection = false;
                }
            }
            return cards;
        }
    }
    
    /// <summary>
    /// カードを表現するクラス
    /// </summary>
    class Card
    {
        /// <summary>
        /// 役
        /// </summary>
        public string strSuit { get; private set; }

        /// <summary>
        /// 数字
        /// </summary>
        public int intNumber { get; private set; }

        public Card(string value)
        {
            this.strSuit = value[0].ToString();
            this.intNumber = int.Parse(value[1].ToString());
        }

        /// <summary>
        /// 自分の数値がTargetの数値より大きいかを判定
        /// </summary>
        /// <param name="Target"></param>
        /// <returns></returns>
        public bool isBiggerThan(Card Target)
        {
            return this.intNumber > Target.intNumber;
        }
        
        public override string ToString()
        {
            return this.strSuit + this.intNumber.ToString();
        }

        public override bool Equals(object obj)
        {
            if (obj == null)
            {
                return false;
            }
            else if (this.GetType() != obj.GetType())
            {
                return false;
            }
            else
            {
                Card targetCard = (Card)obj;
                if (this.strSuit == targetCard.strSuit && this.intNumber == targetCard.intNumber)
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
        }
    }
}



Measured memory_bytes: 18172