using System;

namespace ALDS1_2_C
{
    class Program
    {
        static void Main(string[] args)
        {
            string input = Console.ReadLine();
            int N = int.Parse(input);
            input = Console.ReadLine();
            string[] list = input.Split(' ');
            string[] listBS = input.Split(' ');
            string[] listSS = input.Split(' ');

            bubbleSort(listBS, N);

            if (judge(list,listBS))
            {
                Console.WriteLine("Stable");
            } else
            {
                Console.WriteLine("Not stable");
            }

            selectionSort(listSS, N);
            if (judge(list, listSS))
            {
                Console.WriteLine("Stable");
            }
            else
            {
                Console.WriteLine("Not stable");
            }
        }

        public static void bubbleSort(string[] arr, int N)
        {
            bool flag = true;
            int tmp;
            string tmpstring;

            int[] num = new int[N];
            for (int i = 0; i < N; i++)
            {
                num[i] = int.Parse(arr[i].Substring(1, 1));
            }

            while (flag)
            {
                flag = false;
                for (int i = N - 1; i > 0; i--)
                {
                    if (num[i] < num[i - 1])
                    {
                        tmp = num[i - 1];
                        num[i - 1] = num[i];
                        num[i] = tmp;

                        tmpstring = arr[i - 1];
                        arr[i - 1] = arr[i];
                        arr[i] = tmpstring;
                        flag = true;
                    }
                }
            }
            string output = string.Join(" ", arr);

            Console.WriteLine(output);            
        }

        public static void selectionSort(string[] arr, int N)
        {
            int tmp, minj;
            string tmpstring;

            int[] num = new int[N];
            for (int i = 0; i < N; i++)
            {
                num[i] = int.Parse(arr[i].Substring(1, 1));
            }

            for (int i = 0; i < N; i++)
            {
                minj = i;
                for (int j = i; j < N; j++)
                {
                    if (num[j] < num[minj])
                    {
                        minj = j;
                    }
                }
                if (i != minj)
                {
                    tmp = num[i];
                    num[i] = num[minj];
                    num[minj] = tmp;

                    tmpstring = arr[i];
                    arr[i] = arr[minj];
                    arr[minj] = tmpstring;
                }
            }

            string output = string.Join(" ", arr);
            Console.WriteLine(output);
        }

        public static bool judge(string[] before, string[] after)
        {
            int N = before.Length;
            int[] numb = new int[N];
            int[] numa = new int[N];
            for (int i = 0; i < N; i++)
            {
                numb[i] = int.Parse(before[i].Substring(1, 1));
                numa[i] = int.Parse(after[i].Substring(1, 1));
            }

            for (int i = 0; i < N; i++)
            {
                for (int j = i + 1; j < N; j++)
                {
                    if (numb[i] == numb[j])
                    {
                        for (int p = 0; p < N; p++)
                        {
                            if (numa[p] != numb[i]) continue;
                            for (int q = p + 1;q < N; q++)
                            {
                                if (numa[q] != numb[i]) continue;
                                if (before[i] == after[q] && before[j] == after[p]) return false;
                            }
                        }
                    }
                }
            }
            return true;
        }
    }
}

Measured memory_bytes: 8932