#include<iostream>
#include<vector>
#include<string>
using namespace std;



//int main() {
//
//	int n;
//
//	cin >> n;
//	string s[40];
//	for (int i = 0; i < n; i++) {
//		cin >> s[i];
//
//
//	}
//
//	string in[40];
//	for (int i = 0; i < n; i++) {
//		in[i] = s[i];
//	}
//	int i = 0;
//	while (i <= n - 1) {
//		for (int j = n - 1; j > i; j--) {
//			if (s[j][1] < s[j - 1][1]) {
//				string tmp = s[j];
//				s[j] = s[j - 1];
//				s[j - 1] = tmp;
//				
//			}
//		}
//
//		i++;
//	}
//
//
//	for (int i = 0; i < n; i++) {
//		if (i != n - 1)cout << s[i] << " ";
//		if (i == n - 1)cout << s[i] << endl;
//	}
//
//
//	string x[10], y[10];
//
//	for (int i = 0; i < n; i++) {
//		x[in[i][1] - '0'] += in[i][0];
//		y[s[i][1] - '0'] += s[i][0];
//	}
//	int ans = 1;
//	for (int i = 0; i < 10; i++) {
//		if (x[i] != y[i])ans = 0;
//	}
//	cout << (ans ? "Stable": "Not stable") << endl;
//
//	for (int i = 0; i < n; i++) {
//		s[i] = in[i];
//	}
//	for (int i = 0; i < n; i++) {
//		int minj = i;
//		for (int j = i; j < n; j++) {
//			if (s[j][1] < s[minj][1]) {
//				minj = j;
//			}
//		}
//		if (minj != i) {
//			string tmp = s[i];
//			s[i] = s[minj];
//			s[minj] = tmp;
//		}
//	}
//	for (int i = 0; i < 10; i++) x[i] = y[i] = "";
//
//	ans = 1;
//
//	for (int i = 0; i < n; i++) {
//		if (i != n - 1)cout << s[i] << " ";
//		if (i == n - 1)cout << s[i] << endl;
//	}
//	for (int i = 0; i < n; i++) {
//		x[in[i][1] - '0'] += in[i][0];
//		y[s[i][1] - '0'] += s[i][0];
//	}
//	 ans = 1;
//	for (int i = 0; i < 10; i++) {
//		if (x[i] != y[i])ans = 0;
//	}
//	cout << (ans ? "Stable" : "Not stable") << endl;
//
//
//}
//


//round2

int bublleSort(int A[], int N) {
	int flag = 1;
	int cnt = 0;

	while (flag) {
		flag = 0;
		for (int j = N - 1; j >= 1; j--) {
			if (A[j] < A[j - 1]) {
				int tmp = A[j];
				A[j] = A[j - 1];
				A[j - 1] = tmp;
				flag = 1;
				cnt++;
			}

		}
	}
	return cnt;
}


int selectionSort(int A[], int n) {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int minj = i;
		for (int j = i; j < n; j++) {
			if (A[j] < A[minj]) {
				minj = j;
			}
		}
		if (i != minj) {
			swap(A[i], A[minj]);
			cnt++;
		};
	}

	return cnt;
}

bool judgeStable(vector<char> first[], vector<string> in) {

	bool judge = true;
	for (int i = 0; i < in.size(); i++) {
		char x = in[i][1];
		char c = in[i][0];
		int num = x - '0';
		char moji=first[num].front();
		first[num].erase(first[num].begin());
		if (moji != c) {
			judge = false;
			break;
		}

	}
	return judge;
}
int main() {

	int n;
	cin >> n;
	string s;
	vector<string> inb;
	vector<string> ins;
	vector<char> first1[10];
	vector<char> first2[10];


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

		cin >> s;
		inb.push_back(s);
		ins.push_back(s);
		char x = s[1];
		int num = x - '0';
		first1[num].push_back(s[0]);
		first2[num].push_back(s[0]);


	}
	//Bubble
	int flag = 1;

	while (flag) {
		flag = 0;
		for (int j = n - 1; j >= 1; j--) {
			int numj = inb[j][1] - '0';
			int numj1 = inb[j-1][1] - '0';

			if (numj < numj1) {
				string tmp = inb[j];
				inb[j] = inb[j - 1];
				inb[j - 1] = tmp;
				flag = 1;
			}

		}
	}
	for (int i = 0; i < n; i++) {
		if (i != n - 1)cout << inb[i] << " ";
		else cout << inb[i] << endl;
		
	}

	bool judge = judgeStable(first1, inb);
	if (judge) {
		cout << "Stable"<<endl;
	}
	else {
		cout << "Not stable" << endl;
	}

	for (int i = 0; i < n; i++) {
		int minj = i;
		for (int j = i; j < n; j++) {
			int numj = ins[j][1] - '0';
			if (numj < (int)(ins[minj][1]-'0')) {
				minj = j;
			}
		}
		if (i != minj) {
			swap(ins[i], ins[minj]);

		};
	}
	for (int i = 0; i < n; i++) {
		if (i != n - 1)cout << ins[i] << " ";
		else cout << ins[i] << endl;

	}

	bool judge2 = judgeStable(first2, ins);
	if (judge2) {
		cout << "Stable" << endl;
	}
	else {
		cout << "Not stable" << endl;
	}

}


Measured memory_bytes: 3172