#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DEF_ELM_MAX 36

typedef	struct	_CARD {
	char	mark;
	int		value;
} CARD;

	CARD R[DEF_ELM_MAX];
	CARD R_o[DEF_ELM_MAX];

////////////////////////////////////////////////////////////////////////////////
//
/////////////////////////////////////////////////////////////////////////////////
void copyArray(CARD *dst, CARD *src, int N)
{
	int i;
	for ( i = 0 ; i < N ; i++ ) {
		dst[i] = src[i];
	}
}

////////////////////////////////////////////////////////////////////////////////
//
/////////////////////////////////////////////////////////////////////////////////
int isStable(CARD *A_in, CARD *A_out, int N)
{
	int i;
	int j;
	int a;
	int b;

	for ( i = 0 ; i < N ; i++ ) {
		for ( j = i+1 ; j < N ; j++ ) {
			for ( a = 0 ; a < N ; a++ ) {
				for ( b = a+1 ; b < N ; b++ ) {
					if ( A_in[i].value == A_in[j].value && memcmp(&A_in[i], &A_out[b], sizeof(CARD)) == 0 && memcmp(&A_in[j], &A_out[a], sizeof(CARD)) == 0) {
						return 0;
					}
				}
			}
		}
	}

	return 1;
}

////////////////////////////////////////////////////////////////////////////////
//
/////////////////////////////////////////////////////////////////////////////////
void swap(CARD *x, CARD *y)
{
	CARD tmp;
	tmp = *x;
	*x = *y;
	*y = tmp;
	return;
}

////////////////////////////////////////////////////////////////////////////////
//
/////////////////////////////////////////////////////////////////////////////////
void bubbleSort(CARD *A, int N) // N ??????????´?????????? 0-????????????????????? A
{
	int flag = 1; // ????????£??\????´?????????¨??????
	int i;
	int j;

	i = 0;
	while (flag) {
		flag = 0;
		for ( j = N-1 ; j > i ; j-- ) {
			if (A[j].value < A[j-1].value) {
				swap(&A[j], &A[j-1]);
				flag = 1;
			}
		}
		i++;
	}
}

////////////////////////////////////////////////////////////////////////////////
//
/////////////////////////////////////////////////////////////////////////////////
void selectionSort(CARD *A, int N) // N??????????´??????????0-?????????????????????A
{
	int i;
	int j;
	int minj;
	int flag;

	for ( i = 0 ; i < N ; i++ ) {
		minj = i;
		flag = 0;
		for ( j = i ; j < N ; j++ ) {
			if ( A[j].value < A[minj].value ) {
				minj = j;
				flag = 1;
			}
		}
		if (flag) {
			swap(&A[i], &A[minj]);
		}
	}
}

////////////////////////////////////////////////////////////////////////////////
//
/////////////////////////////////////////////////////////////////////////////////
void printout(CARD *R_o, CARD *R, int N)
{
	int i;
	for ( i = 0 ; i < N ; i++ ) {
		if (i > 0) {
			printf(" ");
		}
		printf("%c%d", R[i].mark, R[i].value);
	}
	printf("\n%s\n", ((isStable(R_o, R, N) == 1) ? "Stable" : "Not Stable"));
}

////////////////////////////////////////////////////////////////////////////////
//
/////////////////////////////////////////////////////////////////////////////////
int main(void)
{
	int N;
	int i;
//
	scanf("%d", &N);
	for ( i = 0 ; i < N ; i++ ) {
		scanf(" %c%d", &R_o[i].mark, &R_o[i].value);
	}
//
	copyArray(R, R_o, N);
//
	bubbleSort(R, N);

	printout(R_o, R, N);

//
	copyArray(R, R_o, N);
//
	selectionSort(R, N);

	printout(R_o, R, N);

	return 0;
}