using System;

namespace ALDS1_2_C
{
    class Program
    {
        static void Main(string[] args)
        {
            string str = Console.ReadLine();
            int n = int.Parse(str);

            string[] input = Console.ReadLine().Split(' ');

            string[] bubbleSort = BubbleSort(input, n);
            string[] selectionSort = SelectionSort(input, n);
            string[] insertionSort = InsertionSort(input, n);

            Output(bubbleSort);

            bool stable = true;
            for (int i = 0; i < n; ++i)
            {
                if (insertionSort[i] != bubbleSort[i])
                {
                    stable = false;
                    break;
                }
            }

            if (stable)
            {
                Console.WriteLine("Stable");
            }
            else
            {
                Console.WriteLine("Not stable");
            }

            Output(selectionSort);
            
            stable = true;
            for (int i = 0; i < n; ++i)
            {
                if (insertionSort[i] != selectionSort[i])
                {
                    stable = false;
                    break;
                }
            }

            if (stable)
            {
                Console.WriteLine("Stable");
            }
            else
            {
                Console.WriteLine("Not stable");
            }

        }

        static private string[] BubbleSort(string[] C, int n)
        {
            string[] output = new string[n];
            for (int i = 0; i < n; ++i)
            {
                output[i] = C[i];
            }

            for (int i = 0; i < n; ++i)
            {
                for (int j = n - 1; j > i; --j)
                {
                    if (output[j][1] < output[j - 1][1])
                    {
                        string temp = output[j];
                        output[j] = output[j - 1];
                        output[j - 1] = temp;
                    }
                }
            }

                return output;
        }

        static private string[] SelectionSort(string[] C, int n)
        {
            string[] output = new string[n];
            for (int i = 0; i < n; ++i)
            {
                output[i] = C[i];
            }

            for (int i = 0; i < n; ++i)
            {
                int minj = i;
                for (int j = i; j < n; ++j)
                {
                    if (output[j][1] < output[minj][1])
                    {
                        minj = j;
                    }
                }
                string temp = output[i];
                output[i] = output[minj];
                output[minj] = temp;
            }

                return output;
        }

        static private string[] InsertionSort(string[] C, int n)
        {
            string[] output = new string[n];
            for (int i = 0; i < n; ++i)
            {
                output[i] = C[i];
            }

            for (int i = 1; i < n; ++i)
            {
                string v = output[i];
                int j = i - 1;
                while ((j >= 0) & (output[j][1] > v[1]))
                {
                    output[j + 1] = output[j];
                    j -= 1;
                    if (j < 0)
                    {
                        break;
                    }
                }
                output[j + 1] = v;
            }

                return output;
        }

        static private void Output(string[] C)
        {
            for (int i = 0; i < C.Length; ++i)
            {
                Console.Write(C[i]);
                if (i == C.Length - 1)
                {
                    Console.Write("\n");
                }
                else
                {
                    Console.Write(" ");
                }
            }
        }
    }
}

Measured memory_bytes: 9324