#include<stdio.h>

struct Card{
	char suit;
	char value;
};

int main(){
	struct Card C1[101], C2[101], l;
	int n, i,f=1,j,mini;
	char ch;

	scanf("%d%c", &n, &ch);
	for (i = 0; i < n; i++){
		scanf("%c%c%c", &C1[i].suit, &C1[i].value, &ch);
	}

	for (i = 0; i < n; i++){
		C2[i] = C1[i];
	}
	
	for (i = 0; i <= n - 1;i++){
		for (j = n - 1; j >= i + 1;j--){
			if (C2[j].value < C2[j - 1].value){
				l=C2[j];
				C2[j]=C2[j - 1];
				C2[j-1]=l;
			}
		}
	}
	
	for (i = 0; i < n; i++){
		printf("%c%c",C2[i].suit,C2[i].value);
		if (i < n - 1){ printf(" "); }
	}
	printf("\n");
	printf("Stable\n");


	for (i = 0; i<n-1;i++){
		mini = i;
		for (j = i; j<=n-1;j++){
			if (C1[j].value < C1[mini].value){
				mini = j;
			}
		}
			l=C1[i];
			C1[i]=C1[mini];
			C1[mini]=l;
	}
	for (i = 0; i < n; i++){
		printf("%c%c", C2[i].suit, C2[i].value);
		if (i < n - 1){ printf(" "); }
	}
	printf("\n");
	
	for (i = 0; i < n;i++){
		if (C2[i].suit != C1[i].suit){ f=0; }
	}
	printf("%s", f ? "Stable\n" : "Not stable\n");
	return 0;
}