using System;
using System.Collections.Generic;//

namespace tst
{
    class Program
    {   
        public struct Card
        {   
            //構造体
            public string Suit { get; set; }
            public int Num { get; set; }

        }
        static void Main(string[] args)
        {
            //nは繰り返しの回数
            int n = int.Parse(Console.ReadLine());
            //input//H4 C9 S4 D2 C3
            string str = Console.ReadLine();
            string[] dt_str = str.Split(' ');
            var num1 = new Card[n];
            var num2 = new Card[n];
            for (int i=0; i<n; i++)
            {
                num1[i].Suit = dt_str[i].Substring(0,1);
                num1[i].Num = int.Parse(dt_str[i].Substring(1,1));
                num2[i].Suit = dt_str[i].Substring(0, 1);
                num2[i].Num = int.Parse(dt_str[i].Substring(1, 1));
            }
            //dt_str[i], num[i].Suit, num[i].Numで表示される

            //bouble sort//安定である
            bool flag = true;
            int st = 1;
            while (flag)
            {
                flag = false;
                for (int j = n - 1; j >= st; j--)
                {
                    if (num1[j - 1].Num > num1[j].Num)
                    {   //数値入れ替え
                        int alt = num1[j].Num;
                        num1[j].Num = num1[j - 1].Num;
                        num1[j - 1].Num = alt;
                        //記号入れ替え
                        string altt = num1[j].Suit;
                        num1[j].Suit = num1[j - 1].Suit;
                        num1[j - 1].Suit = altt;
                        flag = true;
                    }
                }
                st += 1;
            }
            Console.Write(num1[0].Suit + num1[0].Num);
            for (int i = 1; i <= n - 1; i++)
            {
                Console.Write(" " + num1[i].Suit + num1[i].Num);
            }
            Console.WriteLine();
            Console.WriteLine("Stable");//隣と比較しH4とS4が入力されたらその順番維持

            //Selection sort//安定でない
            bool stable = true;
            for (int i = 0; i <= n - 1; i++)
            {
                //一番小さい数字のindexをminにいれる
                int min = i;
                for (int j = i; j <= n - 1; j++)
                {
                    if (num2[j].Num < num2[min].Num) min = j;
                }
                //もし一つ目がminなら交換は不要
                if (i != min)
                {   //数値入れ替え
                    int alt = num2[i].Num;
                    num2[i].Num = num2[min].Num;
                    num2[min].Num = alt;
                    //記号入れ替え
                    string altt = num2[i].Suit;
                    num2[i].Suit = num2[min].Suit;
                    num2[min].Suit = altt;
                }
            }
            Console.Write(num2[0].Suit + num2[0].Num);
            for (int i = 1; i <= n - 1; i++)
            {
                Console.Write(" " + num2[i].Suit + num2[i].Num);
            }
            Console.WriteLine();
            string ans = "Stable";
            for(int i=0; i <= n - 1; i++)
            {
                if (num1[i].Suit != num2[i].Suit) stable = false;
            }
            if (!stable) ans = "Not stable";
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 17920