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


namespace ALDS1_2_C_Stable_Sort
{
	class Program
	{
		static void Main ( string[] args )
		{
			//input
			int numCount = int.Parse (Console.ReadLine ());
			string[] inputStr = Console.ReadLine ().Trim ().Split (' ');

			Card[] cards = new Card[numCount];
			for (int lp = 0; lp < numCount; lp++)
			{
				cards[lp] = new Card (inputStr[lp]);
			}

			Card[] sort = new Card[numCount];
			Card[] sort2 = new Card[numCount];
			cards.CopyTo (sort, 0);
			cards.CopyTo (sort2, 0);

			//process
			Card[] bubbleSort = BubbleSort (sort, numCount);
			Card[] selectionSort = SelectionSort (sort2, numCount);

			//output
			Print (bubbleSort);

			//stable or not stable
			bool stableFlag = IsStableSort (cards, bubbleSort);
			if (stableFlag)
			{
				Console.WriteLine ("Stable");
			}
			else
			{
				Console.WriteLine ("Not stable");
			}

			Print (selectionSort);

			//stable or not stable 
			bool stableFlag2 = IsStableSort (cards, selectionSort);
			if (stableFlag2)
			{
				Console.WriteLine ("Stable");
			}
			else
			{
				Console.WriteLine ("Not stable");
			}

		}

		static Card[] BubbleSort ( Card[] cards, int numCount )
		{
			for (int index = 0; index < numCount; index++)
			{
				for (int index2 = numCount - 1; index < index2; index2--)
				{
					if (cards[index2].Number < cards[index2 - 1].Number)
					{
						var tmp = cards[index2];
						cards[index2] = cards[index2 - 1];
						cards[index2 - 1] = tmp;
					}
				}
			}

			return cards;
		}

		static Card[] SelectionSort ( Card[] cards, int numCount )
		{
			for (int index = 0; index < numCount; index++)
			{
				int minIndex = index;
				for (int index2 = index; index2 < numCount; index2++)
				{
					if (cards[index2].Number < cards[minIndex].Number)
					{
						minIndex = index2;
					}
				}
				var tmp = cards[index];
				cards[index] = cards[minIndex];
				cards[minIndex] = tmp;
			}

			return cards;
		}

		static bool IsStableSort ( Card[] originalArray, Card[] sortArray )
		{
			//??????????????????????????????????????°????????????????????????????????????????????????????????\??????
			for (int index = 0; index < originalArray.Length; index++)
			{
				List<Card> list = new List<Card> (originalArray.Length / 2);

				for (int index2 = 0; index2 < originalArray.Length; index2++)
				{
					if (originalArray[index].Number == originalArray[index2].Number)
					{
						list.Add (originalArray[index2]);
					}
				}

				/* 
				 * ?????????????????????????????¢??¢?´¢?????????????????????????????????????????¢??¢?´¢??????
				 * ???????????????????????\??????????¬????????????????????????????????????¢?´¢??????
				 */

				if (1 < list.Count)
				{
					int listIndex = 0;
					for (int index3 = 0; index3 < sortArray.Length; index3++)
					{
						if (sortArray[index3] == list[listIndex])
						{
							listIndex++;
						}
						//??¨??????????????£???
						if (listIndex == list.Count)
						{
							break;
						}
					}

					//???????????°false
					if (listIndex != list.Count)
					{
						return false;
					}
				}
			}

			return true;
		}

		static void Print (Card[] cards)
		{
			for (int lp = 0; lp < cards.Length - 1; lp++)
			{
				Console.Write (cards[lp].Mark + cards[lp].Number + " ");
			}
			Console.WriteLine (cards[cards.Length - 1].Mark + cards[cards.Length - 1].Number);
		}
	}

	class Card
	{
		public Card ( string numArray )
		{
			this.Mark = numArray[0].ToString();
			this.Number = int.Parse (numArray[1].ToString ());
		}

		public string Mark { private set; get; }
		public int Number { private set; get; }
	}
}

Measured memory_bytes: 9168