#include<stdio.h>

/*構造体の定義*/
typedef struct {
	char suit[10];
	int value;
} Card ;


void swap_Card(Card *x, Card *y)
{
	Card temp = *x;
	*x = *y;
	*y = temp;
}

/*バブルソート*/
void BubbleSort(Card A[], int N) {
	int i, j;

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


/*選択ソート*/
void SelectionSort(Card A[], int N) {
	int i, j;
	int minj;

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


/*バブルソートと選択ソートの結果を比較*/
int isStable(Card BC[], Card SC[], int N) {
	int i;

	for (i = 0; i < N; i++) {
		if (BC[i].suit != SC[i].suit) {
			return 0;
		}
	}
	return 1;
}

int main()
{
	int N;
	int i;
	Card BC[36];
	Card SC[36];

	scanf_s("%d", &N);

	for (i = 0; i < N; i++) {
		scanf_s("%s", BC[i].suit, 10);
		scanf_s("%d", &BC[i].value);
	}
	for (i = 0; i < N; i++) {
		SC[i] = BC[i];
	}

	SelectionSort(SC, N);
	BubbleSort(BC, N);

	/* Output */
	for (i = 0; i < N - 1; i++) {
		printf("%c%d ", BC[i].suit, BC[i].value);
	}
	printf("%c%d\n", BC[N - 1].suit, BC[N - 1].value);
	puts("Stable");

	for (i = 0; i < N - 1; i++) {
		printf("%c%d ", SC[i].suit, SC[i].value);
	}
	printf("%c%d\n", SC[N - 1].suit, SC[N - 1].value);

	for (i = 0; i < N; i++) {
		if (BC[i].suit != SC[i].suit) {
			puts("Not stable");
			return 0;
		}
	}
	puts("Stable");

	return 0;
}
