#include<stdio.h>
#include <sstream>
#include <iostream>
#include <cstdlib>
#include <string.h>

using namespace std;

#define BUF_SIZE 1024
#define ARRAY_SIZE 36


void selectionSort(char array[ARRAY_SIZE][3],int n)
{
	int min;
	char tmp[3];
	for(int i = 0; i < n-1; i++){
		min = i;	//?????????
		for(int j = i+1; j < n; j++){
			if(array[j][1] - '0' < array[min][1] - '0'){
				min = j;
			}
		}
		if(i != min){
			strcpy(tmp,array[i]);
			strcpy(array[i],array[min]);
			strcpy(array[min],tmp);
		}
	}
}

void bubbleSort(char array[ARRAY_SIZE][3],int n){

	char tmp[3];
	for(int i = n-1; i >0; i--){
		for(int j = 0; j < i; j++){
			if(array[j][1] - '0' > array[j+1][1] - '0'){
				strcpy(tmp,array[j+1]);
				strcpy(array[j+1],array[j]);
				strcpy(array[j],tmp);
			}
		}
	}
}

bool checkStable(const char array[ARRAY_SIZE][3],const char sortedArray[ARRAY_SIZE][3],int n){

	char order1[9][5];
	char order2[9][5];

	for(int i = 0; i < 9; i++){
		order1[i][0] = '\0';
		order1[i][0] = '\0';
	}

	bool ret = true;

	int a1=0,a2=0,a3=0,a4=0,a5=0,a6=0,a7=0,a8=0,a9=0;
	for(int i = 0; i < n; i++){
		//printf("array1[%d]:%s\n",i,array[i]);
		switch(array[i][1]){
		case '1':
			order1[0][a1++] = array[i][0];
			order1[0][a1] = '\0';
			break;
		case '2':
			order1[1][a2++] = array[i][0];
			order1[1][a2] = '\0';
			break;
		case '3':
			order1[2][a3++] = array[i][0];
			order1[2][a3] = '\0';
			break;
		case '4':
			order1[3][a4++] = array[i][0];
			order1[3][a4] = '\0';
			break;
		case '5':
			order1[4][a5++] = array[i][0];
			order1[4][a5] = '\0';
			break;
		case '6':
			order1[5][a6++] = array[i][0];
			order1[5][a6] = '\0';
			break;
		case '7':
			order1[6][a7++] = array[i][0];
			order1[6][a7] = '\0';
			break;
		case '8':
			order1[7][a8++] = array[i][0];
			order1[7][a8] = '\0';
			break;
		case '9':
			order1[8][a9++] = array[i][0];
			order1[8][a9] = '\0';
			break;
		}
	}

	int b1=0,b2=0,b3=0,b4=0,b5=0,b6=0,b7=0,b8=0,b9=0;
	for(int i = 0; i < n; i++){
		//printf("sortedarray[%d]:%s\n",i,sortedArray[i]);
		switch(sortedArray[i][1]){
		case '1':
			order2[0][b1++] = sortedArray[i][0];
			order2[0][b1] = '\0';
			break;
		case '2':
			order2[1][b2++] = sortedArray[i][0];
			order2[1][b2] = '\0';
			break;
		case '3':
			order2[2][b3++] = sortedArray[i][0];
			order2[2][b3] = '\0';
			break;
		case '4':
			order2[3][b4++] = sortedArray[i][0];
			order2[3][b4] = '\0';
			break;
		case '5':
			order2[4][b5++] = sortedArray[i][0];
			order2[4][b5] = '\0';
			break;
		case '6':
			order2[5][b6++] = sortedArray[i][0];
			order2[5][b6] = '\0';
			break;
		case '7':
			order2[6][b7++] = sortedArray[i][0];
			order2[6][b7] = '\0';
			break;
		case '8':
			order2[7][b8++] = sortedArray[i][0];
			order2[7][b8] = '\0';
			break;
		case '9':
			order2[8][b9++] = sortedArray[i][0];
			order2[8][b9] = '\0';
			break;
		}
	}

	for(int i = 0; i < 9; i++){


		if(strcmp(order1[i], order2[i]) != 0){
			ret = false;
			break;
		}

		//printf("order1[%d] : %s\n",i+1,order1[i]);
		//printf("order2[%d] : %s\n",i+1,order2[i]);

	}
	return ret;
}

int main(){

	char array[ARRAY_SIZE][3];
	char selectArray[ARRAY_SIZE][3];
	char bubbleArray[ARRAY_SIZE][3];

	char buf[BUF_SIZE];
	int n = atoi(fgets(buf,BUF_SIZE,stdin));

	for(int i = 0; i < n; i++)
	{
		cin >> array[i];
		strcpy(selectArray[i],array[i]);
		strcpy(bubbleArray[i],array[i]);
	}

	bubbleSort(bubbleArray,n);
	selectionSort(selectArray,n);


	for(int i = 0; i < n; i++){
		if(i != n-1){
			printf("%s ",bubbleArray[i]);
		}else{
			printf("%s\n",bubbleArray[i]);
		}
	}
	if(checkStable(array,bubbleArray,n)){
		printf("Stable\n");
	}else{
		printf("Not stable\n");
	}


	for(int i = 0; i < n; i++){
		if(i != n-1){
			printf("%s ",selectArray[i]);
		}else{
			printf("%s\n",selectArray[i]);
		}
	}

	if(checkStable(array,selectArray,n)){
			printf("Stable\n");
		}else{
			printf("Not stable\n");
	}

}