#include <stdio.h>

struct TrumpCard{
	
	int num;
	int order;
	char mark;
	
};
typedef struct TrumpCard Card;


void display(Card data[], int n);

void bubbleSort(Card data[], int n);
void selectionSort(Card data[], int n);

void judge(int b);

int isStable(Card data[], int n);

int getMin(Card data[], int from, int to);



int main(){
	
	int n;
	int i;
	int orders[10] = {0};
	char dummy;
	Card data[40];
	Card bubbleData[40];
	Card selectionData[40];
	
	scanf("%d%c", &n, &dummy);
	
	for(i=0; i<n; i++){
		
		scanf("%c%d%c", &data[i].mark, &data[i].num, &dummy);
		data[i].order = ++(orders[data[i].num]);
		
		bubbleData[i] = data[i];
		selectionData[i] = data[i];
		
	}
	
	
	
	bubbleSort(bubbleData, n);
	
	display(bubbleData, n);
	
	judge(isStable(bubbleData, n));
	
	
	
	selectionSort(selectionData, n);
	
	display(selectionData, n);
	
	judge(isStable(selectionData, n));
	
	
	
	
	
	
}



void display(Card data[], int n){
	
	int i;
	
	for(i=0; i<n; i++){
		
		if(i){
			
			printf(" ");
			
		}
		
		printf("%c%d", data[i].mark, data[i].num);
		//printf("%c%d(%d)", data[i].mark, data[i].num, data[i].order);
		
	}
	
	printf("\n");
	
}

void bubbleSort(Card data[], int n){
	
	int i, j;
	Card temp;
	
	for(i=0; i<n; i++){
		
		for(j=n-1; j>i; j--){
			
			if(data[j-1].num > data[j].num){
				
				temp = data[j];
				data[j] = data[j-1];
				data[j-1] = temp;
				
			}
			
		}
		
	}
	
	
}



void selectionSort(Card data[], int n){
	
	int i, min;
	Card temp;
	
	for(i=0; i<n/2; i++){
		
		min = getMin(data, i , n);
		
		temp = data[min];
		data[min] = data[i];
		data[i] = temp;
		
	}
	
}



void judge(int b){
	
	if(b){
		
		printf("Stable\n");
		
	}
	else{
		
		printf("Not Stable\n");
		
	}
	
}



int isStable(Card data[], int n){
	
	int i;
	int ret = 1;
	
	for(i=0; i<n; i++){
		
		if(data[i].order >= 2){
			
			if(data[i-1].num != data[i].num){
				
				ret = 0;
				break;
				
			}
			else if(data[i-1].order != (data[i].order-1)){
				
				ret = 0;
				break;
				
			}
			
		}
		
	}
	
	return ret;
	
}



int getMin(Card data[], int from, int to){
	
	int i;
	int min = from;
	
	for(i=from+1; i<to; i++){
		
		if(data[i].num < data[min].num){
			
			min = i;
			
		}
		
	}
	
	return min;
	
}