using System;
using System.Linq;

namespace aoj
{
    class Program
    {
        public class Card
        {
            public string body;
            public char mark;
            public int value;

            public Card(string _body)
            {
                this.body = _body;
                this.mark = _body[0];
                this.value = int.Parse(_body[1].ToString());
            }
        }

        static void Main(string[] args)
        {
            var length = int.Parse(Console.ReadLine());
            string[] array = Console.ReadLine().Split(' ');
            Card[] cards4Bubble = new Card[length];
            Card[] cards4Select = new Card[length];

            for (var i = 0; i < length; ++i)
            {
                cards4Bubble[i] = new Card(array[i]);
                cards4Select[i] = new Card(array[i]);
            }

            bubbleSort(ref cards4Bubble, length);
            selectSort(ref cards4Select, length);
        }

        static void bubbleSort(ref Card[] _array, int _length)
        {
            string[] marksOrigin = new string[13];
            for (var i = 0; i < _length; ++i)
            {
                marksOrigin[_array[i].value] += _array[i].mark;
            }

            // 逆の隣接要素が存在する
            var flag = true;
            while (flag)
            {
                flag = false;
                for (var i = _length - 1; 0 < i; --i)
                {
                    if (_array[i].value < _array[i - 1].value)
                    {
                        Swap(ref _array[i], ref _array[i - 1]);
                        flag = true;
                    }
                }
            }

            for (var i = 0; i < _length; ++i)
            {
                Console.Write(_array[i].body);
                if (i != _length - 1)
                {
                    Console.Write(" ");
                }
            }
            Console.WriteLine();

            string[] marks = new string[13];
            for (var i = 0; i < _length; ++i)
            {
                marks[_array[i].value] += _array[i].mark;
            }

            for (var i = 0; i < 13; ++i)
            {
                if (marksOrigin[i] != marks[i])
                {
                    Console.WriteLine("Not stable");
                    return;
                }
            }
            Console.WriteLine("Stable");
        }

        static void selectSort(ref Card[] _array, int _length)
        {
            string[] marksOrigin = new string[13];
            for (var i = 0; i < _length; ++i)
            {
                marksOrigin[_array[i].value] += _array[i].mark;
            }

            for (var i = 0; i < _length; ++i)
            {
                var minIndex = i;

                // iよりindexが大きい要素の中から最小値を探す
                for (var k = i; k < _length; ++k)
                {
                    if (_array[k].value < _array[minIndex].value)
                    {
                        minIndex = k;
                    }
                }

                if (i != minIndex)
                {
                    Swap(ref _array[i], ref _array[minIndex]);
                }
            }
            
            for (var i = 0; i < _length; ++i)
            {
                Console.Write(_array[i].body);
                if (i != _length - 1)
                {
                    Console.Write(" ");
                }
            }
            Console.WriteLine();

            string[] marks = new string[13];
            for (var i = 0; i < _length; ++i)
            {
                marks[_array[i].value] += _array[i].mark;
            }

            for (var i = 0; i < 13; ++i)
            {
                if (marksOrigin[i] != marks[i])
                {
                    Console.WriteLine("Not stable");
                    return;
                }
            }
            Console.WriteLine("Stable");
        }

        static void Swap<T>(ref T _a, ref T _b)
        {
            var tmp = _a;
            _a = _b;
            _b = tmp;
        }
    }
}



Measured memory_bytes: 15960