using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;

namespace LogicSummoner
{
    class Program
    {
        class Tramp
        {
            public char Mark { get; set; }
            public int Number { get; set; }
            public Tramp(char mark, int number)
            {
                Mark = mark;
                Number = number;
            }
            public Tramp(Tramp t) : this(t.Mark, t.Number)
            {

            }
            public void Swap(Tramp other)
            {
                var m = Mark;
                var n = Number;
                Mark = other.Mark;
                Number = other.Number;
                other.Mark = m;
                other.Number = n;
            }
            public override int GetHashCode()
            {
                return Number;
            }
            public override bool Equals(object obj)
            {
                if (obj == null)
                {
                    return false;
                }
                var t = obj as Tramp;
                if (t == null)
                {
                    return false;
                }
                return Number == t.Number;
            }
            public override string ToString()
            {
                return string.Format("{0}{1}", Mark, Number);
            }
        }

        static void Main(string[] args)
        {
            var N = GetNumber();
            var a = GetStrings(N).Select(xs => new Tramp(xs[0], int.Parse(xs.Substring(1)))).ToArray();
            var b = a.Select(x => new Tramp(x)).ToArray();
            var c = a.Select(x => new Tramp(x)).OrderBy(x => x.Number).ToArray();
            var outputC = string.Join(" ", c.Select(x => x.ToString()).ToArray());

            BubbleSort(a);
            var outputA = string.Join(" ", a.Select(x => x.ToString()).ToArray());
            System.Console.WriteLine(outputA);
            System.Console.WriteLine(outputA == outputC ? "Stable" : "Not stable");

            SelectionSort(b);
            var outputB = string.Join(" ", b.Select(x => x.ToString()).ToArray());
            System.Console.WriteLine(outputB);
            System.Console.WriteLine(outputB == outputC ? "Stable" : "Not stable");
        }

        //static StreamReader Console = new StreamReader("input.txt");

        static int BubbleSort(Tramp[] A)
        {
            var count = 0;
            for (int i = 0; i < A.Length - 1; i++)
            {
                for (int j = A.Length - 1; j >= i + 1; j--)
                {
                    if (A[j].Number < A[j - 1].Number)
                    {
                        count++;
                        A[j].Swap(A[j - 1]);
                    }
                }
            }
            return count;
        }

        static int SelectionSort(Tramp[] A)
        {
            var count = 0;
            for (var i = 0; i < A.Length; i++)
            {
                var mini = i;
                for (var j = i; j < A.Length; j++)
                {
                    if (A[j].Number < A[mini].Number)
                    {
                        mini = j;
                    }
                }

                if (i != mini)
                {
                    A[i].Swap(A[mini]);
                }
            }
            return count;
        }

        static int GetNumber()
        {
            return int.Parse(Console.ReadLine().Trim());
        }

        static double GetDounble()
        {
            return double.Parse(Console.ReadLine().Trim());
        }

        static int[] GetNumbersInt(int n = 0)
        {
            return Console.ReadLine().Trim().Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries).Select(x => int.Parse(x)).ToArray();
        }

        static long[] GetNumbersLong(int n = 0)
        {
            return Console.ReadLine().Trim().Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries).Select(x => long.Parse(x)).ToArray();
        }

        static double[] GetNumbersDouble(int n = 0)
        {
            return Console.ReadLine().Trim().Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries).Select(x => double.Parse(x)).ToArray();
        }

        static string[] GetStrings(int n = 0)
        {
            return Console.ReadLine().Trim().Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries).ToArray();
        }
    }
}

Measured memory_bytes: 10444