#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
using namespace std;

struct card{
	string suit;
	int	number;
};

void swapCard(card &a,card &b){
	string str;
	int num;
	str = a.suit;
	num = a.number;
	a.suit = b.suit;
	a.number = b.number;
	b.suit = str;
	b.number = num;
}

void printArray(struct card cardArray[],int n){
	cout<<cardArray[0].suit<<cardArray[0].number;
	for(int i = 1; i < n; i++){
		cout<<" "<<cardArray[i].suit<<cardArray[i].number;
	}
	cout<<endl;
}

void bubbleSort(card cardArray[],int n){
	for(int i = 0; i < n ; i++){
		for(int j = n-1; j > i; j--){
			if(cardArray[j].number < cardArray[j-1].number) swapCard(cardArray[j],cardArray[j-1]);
		}
	}
}

void selectionSort(card cardArray[],int n){
	for(int i = 0; i < n ; i++){
		int minj = i;
		for(int j =i; j < n; j++){
			if(cardArray[j].number < cardArray[minj].number) minj = j;
		}
		swapCard(cardArray[i],cardArray[minj]);
	}
}

bool isSameCard(card a,card b){
	if( a.number == b.number && a.suit == b.suit) return true;
	return false;
}
bool isSameNumber(card a,card b){
	if(a.number == b.number) return true;
	return false;
}
bool isSameSuit(card a,card b){
	if(a.suit == b.suit) return true;
	return false;
}

int seriesNumber(card cardArray[],int index,int n){
	if(index >= n-1)return 0;
	if( isSameNumber(cardArray[index],cardArray[index+1])){
		return seriesNumber(cardArray,index + 1, n) + 1;
	}
	return 1;
}

bool isStableSub(card cardArray1[],int index1,int seriesNum,card cardArray2[],int index2,int n){
	if(seriesNum == 0 ) return true;
	if(isSameNumber(cardArray1[index1],cardArray2[index2])){
		if(isSameSuit(cardArray1[index1],cardArray2[index2]) == false){
			return false;
		}else{
			return isStableSub(cardArray1,index1 + 1, seriesNum - 1, cardArray2,index2 + 1,n);
		}
	}
	return isStableSub(cardArray1,index1,seriesNum,cardArray2,index2 +  1,n);
}

bool isStable(card cardArray1[],card cardArray2[],int n){
	int i = 0;
	while( i < n-1){
		int seriesNum = seriesNumber(cardArray1,i,n);
		//cout << seriesNum << endl;
		if(seriesNum > 1 ){
			if(isStableSub(cardArray1,i,seriesNum,cardArray2,0,n) == false) return false;
		}
		i = i + seriesNum;
	}
	return true;
}

int main()
{
	int n;
	cin >> n ;
	struct card *originalArray = new struct card[n];
	struct card *bubbleArray = new struct card[n];
	struct card *selectArray = new struct card[n];
	for(int i = 0 ; i < n; i++){
		string str;
		cin >> str;
		//suit の代入
		originalArray[i].suit = str[0];
		bubbleArray[i].suit = str[0];
		selectArray[i].suit = str[0];
		
		//number の代入
		originalArray[i].number = stoi(str.substr(1,str.size() - 1));
		bubbleArray[i].number = stoi(str.substr(1,str.size() - 1));
		selectArray[i].number = stoi(str.substr(1,str.size() - 1));
	}
	//cout<<bubbleArray[0].suit << bubbleArray[0].number<<endl;
	bubbleSort(bubbleArray,n);
	selectionSort(selectArray,n);
	printArray(bubbleArray,n);
	if(isStable(bubbleArray,originalArray,n)){
		cout<<"Stable"<<endl;
	}else{
		cout<<"Not stable"<<endl;
	}
	printArray(selectArray,n);
	if(isStable(selectArray,originalArray,n)){
		cout<<"Stable"<<endl;
	}else{
		cout<<"Not stable"<<endl;
	}
	delete[] bubbleArray,selectArray,originalArray;
	return 0;
}





Measured memory_bytes: 3188