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

int n, A[36], B[36];
char a[36], b[36];

string isStable(){
  for (int i=0;i<n;i++){
    if(A[i]==B[i] && a[i]==b[i]) continue;
    return "Not stable";
  }
  return "Stable";
}

int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i]>>A[i];
    b[i]=a[i];
    B[i]=A[i];
  }
  for(int i=0;i<n;i++){
    for(int j=n-1;j>i;j--){
      if(A[j]<A[j-1]){
	swap(A[j], A[j-1]);
	swap(a[j], a[j-1]);
      }
    }
  }
  for(int i=0;i<n;i++){
    int minj = i;
    for(int j=i+1;j<n;j++){
      if(B[j]<B[minj]) minj = j;
    }
    swap(B[i], B[minj]);
    swap(b[i], b[minj]);
  }
  for(int i=0;i<n;i++){
    if(i) cout<<" ";
    cout<<a[i]<<A[i];
  }
  cout<<endl<<"Stable"<<endl;
  for(int i=0;i<n;i++){
    if(i) cout<<" ";
    cout<<b[i]<<B[i];
  }
  cout<<endl<<isStable()<<endl;
  return 0;
}

