#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 36

void BubbleSort();
void SelectionSort();

char A[MAX][2],BS[MAX][2],SS[MAX][2];
int count=0,n;

int main(){

 	int i;

 		scanf("%d",&n);
 		for( i = 0; i < n; i++) scanf(" %s%d",A[i][0],A[i][1]);

 		BubbleSort();
 		for( i = 0; i < n; i++) printf(" %s%d",BS[i],BS[0][1]);
 		printf("\nStable\n");
 			
 		SelectionSort();
 		for( i = 0; i < n; i++) printf("%s%d",SS[i][0],SS[i][1]);
 		if(count == 0) printf("\nStable\n");
 		else printf("\nNot Stable\n");	
 			
 		return 0;
}

void BubbleSort(){

	int swap,i,j;

	for( i = 0; i < n-1; i++){
		for( j = n-1; j >= i; j-- ){
			if(A[j] < A[j-1]){
				BS[j] = A[j-1];
				BS[j-1] = A[j];
			}
		}
	}
}

void SelectionSort(){

	int swap,minj,i,j;

	for(i = 0; i < n-2; i++){
		minj = i;
		for(j = i; j < n-1; j++){
			if(A[j] < A[minj]){
				minj = j;	
			}
		}
		if( i != minj){
			SS[i] = A[minj];
			SS[minj] = A[i];
		}
	}
}

