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

namespace Practice
{
    class Program
    {

        static void Main(string[] args)
        {
            SolveA(args);
            //SolveB(args);
            //SolveC(args);
            //SolveD(args);
        }
        
        public struct Card
        {
            public int d;
            public char suit;
            public Card(string sz)
            {
                suit = sz[0];
                d = int.Parse(sz[1].ToString());
            }
            public override string ToString()
            {
                return suit + d.ToString();
            }
            public bool Same(Card c)
            {
                return c.d == d && c.suit == suit;
            }
        }

        static void SolveA(string[] args)
        {
            string sz = (Console.ReadLine());
            int n = int.Parse(sz);
            string[] szarr = Console.ReadLine().Split(' ');
            Card[] src = new Card[n];
            Card[] dst = new Card[n];
            Card[] dst2 = new Card[n];
            for (int i=0;i<szarr.Length;++i)
            {
                src[i] = new Card(szarr[i]);
                dst[i] = src[i];
                dst2[i] = src[i];
            }
            babbleSort(dst);
            CheckStable(src, dst);
            selectionSort(dst2);
            CheckStable(src, dst2);
        }
        private static void babbleSort(Card[] a)
        {
            for(int i=0;i<a.Length;++i)
            {
                for(int j=a.Length - 1; j >= i+1;--j)
                {
                    if( a[j].d < a[j-1].d)
                    {
                        Card tmp = a[j];
                        a[j] = a[j - 1];
                        a[j - 1] = tmp;
                    }
                }
            }
            Writeline(a);
        }
        private static void selectionSort(Card[] a)
        {
            for(int i=0;i<a.Length;++i)
            {
                int minj = i;
                for(int j=i;j<a.Length;++j)
                {
                    if( a[j].d < a[minj].d)
                    {
                        minj = j;
                    }
                }
               
                    Card tmp = a[i];
                    a[i] = a[minj];
                    a[minj] = tmp;
                    
                
            }
            Writeline(a);
        }
        private static void Writeline(Card[] a)
        {
            string sz = "";
            for(int i=0;i<a.Length;++i)
            {
                sz += a[i].ToString();
                if( i < a.Length - 1)
                {
                    sz += " ";
                }
            }
            Console.WriteLine(sz);
        }

        private static void CheckStable(Card[] src, Card[] dst)
        {
            for(int i=0;i<src.Length;++i)
            {
                for(int j=i+1;j<src.Length;++j)
                {
                    for(int a = 0;a<dst.Length;++a)
                    {
                        for(int b = a+1;b<dst.Length;++b)
                        {
                            if( src[i].d == src[j].d && src[i].Same( dst[b]) && src[j] .Same( dst[a]))
                            {
                                Console.WriteLine("Not stable");
                                return;
                            }
                        }
                    }
                }
            }
            Console.WriteLine("Stable");
        }
    }

}



Measured memory_bytes: 9180