#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n;
vector<string> v1, v2;

void swap(int &a, int &b){
	int tmp = a;
	a = b;
	b = tmp;
}

void BubbleSort(){
	int i=0;
	while(true){
		if(i == n) break;
		for(int j=n-1; j > i; --j){
			if(v1[j][1] < v1[j-1][1])
				swap(v1[j], v1[j-1]);
		}
		++i;
	}
}

void SelectionSort(){
	int num;
	char minv;
	for(int i=0; i < n; ++i){
		minv = 'a';
		for(int j=i+1; j < n; ++j){
			if(v2[j][1] < minv){
				num = j;
				minv = v2[j][1];
			}
		}
		if(v2[i][1] > v2[num][1]) swap(v2[i], v2[num]);
	}
}

void print(vector<string> vec){
	for(int i=0; i<n; ++i){
		cout << vec[i];
		if(i != n-1) cout << " ";
	}
	cout << "\n";
}

int main(){
	cin >> n;
	string vin;
	for(int i=0; i<n; ++i){
		cin >> vin;
		v1.push_back(vin);
		v2.push_back(vin);
	}

	BubbleSort();
	print(v1);
	cout << "Stable" << endl;
	SelectionSort();
	print(v2);

	if(v1 == v2) cout << "Stable" << endl;
	else cout << "Not stable" << endl;

	return 0;
}
