#include <iostream>

using namespace std;

typedef struct {
	int value;
	char suit;
}card;

void BubbleSort(card C[], int N) {
	for (int i = 0; i < N; ++i) {
		for (int j = N - 1; j > i; --j) {
			if (C[j].value < C[j - 1].value) swap(C[j], C[j - 1]);
		}
	}
}

void selectionSort(card C[], int N) {
	for (int i = 0; i < N; ++i) {
		int minj = i;
		for (int j = i; j < N; ++j)
			if (C[j].value < C[minj].value) minj = j;
		if (i != minj) swap(C[i], C[minj]);
	}
}

void printC(card C[], int N) {
	for (int i = 0; i < N; ++i) {
		if (i) cout << " ";
		cout << C[i].suit << C[i].value;
	}
	cout << endl;
}

int main() {
	card C1[36], C2[36];
	int N; cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> C1[i].suit >> C1[i].value;
		C2[i] = C1[i];
	}
	BubbleSort(C1, N);
	printC(C1, N);
	cout << "Stable" << endl;
	selectionSort(C2, N);
	printC(C2, N);
	bool flag = true;
	for (int i = 0; i < N; ++i)
		if (C1[i].suit != C2[i].suit) flag = false;
	cout << (flag ? "Stable" : "Not stable") << endl;

	return 0;
}
