#include "bits/stdc++.h"
using namespace std;

struct Card{
	char type;
	int value;
};

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

vector<Card> SelectionSort(vector<Card> C,int N){
	for(int i=0;i<N;++i){
		int minj=i;
		for(int j=i+1;j<N;++j){
			if(C[j].value<C[minj].value) minj=j;
		}
		swap(C[i],C[minj]);
	}
	return C;
}

int main(){
	int N;cin>>N;
	vector<Card> C(N);
	for(int i=0;i<N;++i){
		string str;
		cin>>str;
		C[i].type=str[0];
		C[i].value=str[1]-'0';
	}
	
	auto stable=BubbleSort(C,N);
	auto ustable=SelectionSort(C,N);
	for(int i=0;i<N;++i){
		if(i==0) cout<<stable[i].type<<stable[i].value;
		else cout<<" "<<stable[i].type<<stable[i].value;
	}
	puts("");
	puts("Stable");
	bool flag=true;
	for(int i=0;i<N;++i){
		if(i==0) cout<<ustable[i].type<<stable[i].value;
		else cout<<" "<<ustable[i].type<<ustable[i].value;
		if(stable[i].type!=ustable[i].type) flag=false;
	}
	puts("");
	if(!flag) puts("Not stable");
	else puts("Stable");
}

