using System;

public class StableSort {

    public const int CARD_MAX = 36;
       
    public struct Card {
		public char mark;
		public int number;

		public Card(char _mark, int _number) {
		    mark = _mark;
	    	number = _number;
		}

		public void print() {
			Console.Write (this.mark + "" + this.number + " ");
		}
    }

	public Card[] before_T = new Card[0];
	public Card[] after_T = new Card[0];

	public Card[] bubbleSortedArray = new Card[0];
	public Card[] selectionSortedArray = new Card[0];

	public StableSort(int n) {
		before_T = new Card[n];
		after_T = new Card[n];
		bubbleSortedArray = new Card[n];
		selectionSortedArray = new Card[n];
	}

	public void bubbleSort() {
		for (int i = 0; i < before_T.Length; i++) {
			for (int j = before_T.Length - 1; i < j; j--) {
				if (before_T [j].number < before_T [j - 1].number) {
					Card tmp = before_T [j];
					before_T [j] = before_T [j - 1];
					before_T [j - 1] = tmp;
				}
			}
		}
		// ???????????????????????????????????????
		before_T.CopyTo(bubbleSortedArray, 0);

		// before??¨after?????\????????????
		this.reset();
	}

	public void selectionSort() {
		for (int i = 0; i < before_T.Length; i++) {
			int minj = i;
			for (int j = i; j < before_T.Length; j++) {
				if (before_T [j].number < before_T [minj].number) {
					minj = j;
				}
			}
			Card tmp = before_T [i];
			before_T [i] = before_T [minj];
			before_T [minj] = tmp;
		}
		// ???????????????????????????????????????
		before_T.CopyTo(selectionSortedArray, 0);

		// before??¨after?????\????????????
		this.reset();
	}

	public void show() {
		for (int i = 0; i < after_T.Length; i++) {
			if (i == after_T.Length - 1) {
				Console.WriteLine (after_T [i].mark + "" + after_T [i].number);
				continue;
			}
			after_T [i].print ();			
		}
	}

	public void reset() {
		Card[] tmp = new Card[before_T.Length];
		before_T.CopyTo (tmp, 0);
		after_T.CopyTo (before_T, 0);
		tmp.CopyTo (after_T, 0);
	}
		
    
    public static void Main() {		
		int N = 0;
		N = int.Parse(Console.ReadLine());

		StableSort stableSort = new StableSort (N);

		string[] buf = Console.ReadLine().Split(' ');
			
		for (int i = 0; i < N; i++) {
		    // D2, C3, H4
	    	string cardString = buf[i];			
	    	// D, C, H
			char mark = cardString[0];
	    	// 2, 3, 4
			char numChar = cardString[1];			
			string numString = numChar.ToString();
			int num = int.Parse(numString);
	    	Card card = new Card(mark, num);
			stableSort.before_T[i] = card;			
		}

		// ?????????????????????????????????????????????				
		stableSort.before_T.CopyTo(stableSort.after_T, 0);

		// ????????????????????????????????????????????????
		stableSort.bubbleSort ();
		stableSort.show ();

		// ????????????????????????????????????????????????
		Console.WriteLine("Stable");

		// ?????????????????????????????????????????????
		stableSort.selectionSort();
		stableSort.show ();

		// ?????????????????????????????????????????????????????????(??????????????????????????£?????´??????????????????????????????)		
		for (int i = 0; i < N; i++) {
			// ????????????????????§??´????????????????????????????????¨????????????
			if (!stableSort.bubbleSortedArray [i].mark.Equals (stableSort.selectionSortedArray [i].mark)) {
				Console.WriteLine ("Not stable");
				return;
			}
		}
		Console.WriteLine("Stable");
    }
}

Measured memory_bytes: 9072