#include<stdio.h>

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

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

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

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

	for (i = 0; i < N; i++) {
		minj = i;
		for (j = i; j < N; j++) {
			if (A[j].value < A[minj].value) {
				minj = j;
			}
		}
		temp = A[i];
		A[i] = A[minj];
		A[minj] = temp;
	}
}

//バブルソートと選択ソートの結果を比較
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("%d", &N);

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

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

	//バブルソートの結果
	for (i = 0; i < N; i++) {
		printf("%s%d ", BC[i].suit, BC[i].value);
	}
	printf("\nStable\n");
	
	//選択ソートの結果
	for (i = 0; i < N; i++) {
		printf("%s%d ", SC[i].suit, SC[i].value);
	}
	if (isStable(BC, SC, N)) {
		printf("\nStable\n");
	}
	else {
		printf("\nNot Stable\n");
	}

	return 0;
}
