#include <bits/stdc++.h>
#define N 101
using namespace std;

struct card{
  int num;
  char ch;
  bool operator < (card a)const{return num<a.num;}
  bool operator == (card a)const{return num==a.num&&ch==a.ch;}
};

void BubbleSort(card *A,int n){
  for(int i=0;i<n-1;i++)
    for(int j=n-1;j>=i+1;j--)
      if(A[j] < A[j-1]) swap(A[j],A[j-1]);
}

void SelectionSort(card *A,int n){
  for(int i=0;i<n-1;i++){
    int idx = i;
    for(int j=i;j<n;j++)if(A[j]<A[idx])idx = j;
    swap(A[i],A[idx]);
  }
}

void pr(card *A,int n){
  for(int i=0;i<n;i++){
    if(i)cout<<" ";
    cout<<A[i].ch<<A[i].num;
  }
  cout<<endl;

}

bool isStable(card *A,card *B,int n){
  for(int i=0;i<n;i++) if(!(A[i]==B[i])) return 0;
  return 1;
}

int main(){
  int n;
  cin>>n;
  card A[N],B[N];
  for(int i=0;i<n;i++) cin>>A[i].ch>>A[i].num,B[i] = A[i];
  BubbleSort(A,n);
  SelectionSort(B,n);
  
  pr(A,n);
  cout<<"Stable"<<endl;
  pr(B,n);
  cout<<(isStable(A,B,n)? "Stable":"Not stable")<<endl;
    
  return 0;
}