using System;
using System.Linq;
using System.Collections.Generic;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var A = Console.ReadLine().Split().Select(z => new Tuple<int, string>(int.Parse(z[1].ToString()), z[0].ToString())).ToList();

            var bubble = BubbleSort(new List<Tuple<int, string>>(A), N);
            var select = SelectionSort(new List<Tuple<int, string>>(A), N);

            var dict = new Dictionary<int, List<string>>();
            foreach (var a in A)
            {
                if (dict.ContainsKey(a.Item1))
                    dict[a.Item1].Add(a.Item2);
                else
                {
                    dict[a.Item1] = new List<string>();
                    dict[a.Item1].Add(a.Item2);
                }
            }

            OutputList(bubble);
            IsStatable(bubble, dict);

            OutputList(select);
            IsStatable(select, dict);

        }

        static List<Tuple<int, string>> BubbleSort(List<Tuple<int, string>> A, int N)
        {
            for (var i = 0; i < N; i++)
            {
                for (var j = N - 1; j >= i + 1; j--)
                {
                    if (A[j].Item1 < A[j - 1].Item1)
                    {
                        var tmp = A[j];
                        A[j] = A[j - 1];
                        A[j - 1] = tmp;
                    }
                }
            }

            return A;
        }

        static List<Tuple<int, string>> SelectionSort(List<Tuple<int, string>> A, int N)
        {
            for (var i = 0; i < N; i++)
            {
                var minj = i;
                for (var j = i; j < N; j++)
                {
                    if (A[j].Item1 < A[minj].Item1)
                        minj = j;
                }

                if (i != minj)
                {
                    var tmp = A[i];
                    A[i] = A[minj];
                    A[minj] = tmp;
                }
            }

            return A;
        }

        static void OutputList(List<Tuple<int, string>> A)
        {
            var count = 0;
            foreach (var b in A)
            {
                if (count != 0) Console.Write(" ");
                Console.Write($"{b.Item2}{b.Item1}");
                count++;
            }
            Console.WriteLine();
        }

        static void IsStatable(List<Tuple<int, string>> A, Dictionary<int, List<string>> dict)
        {
            foreach (var d in dict)
            {
                if (d.Value.Count < 2) continue;
                var start = 0;
                foreach (var c in d.Value)
                {
                    for (var i = start; i < A.Count; i++)
                    {
                        if (A[i].Item1 != d.Key) continue;
                        if (A[i].Item2 != c)
                        {
                            Console.WriteLine("Not stable");
                            return;
                        }
                        start = i + 1;
                        break;
                    }
                }
            }

            Console.WriteLine("Stable");
        }
    }
}



Measured memory_bytes: 18460