#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<list>
#include<stack>
#include<map>
#include<set>
#include<string>
#include <sstream>
#include<bitset>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>

using namespace std;

int gcd(int x,int y){
  int mi,ma;
  ma = max(x,y);
  mi = min(x,y);
  if(ma % mi == 0){
    return mi;
  }
  else{
    return gcd(mi,ma % mi);
  }
}

bool isStable(multimap<string,string> org,multimap<string,string> sorted){

  map<string,string>::iterator it;
  map<string,string>::iterator it2;
  string key,prevkey;
  it = org.begin();
  it2 = sorted.begin();
  prevkey = "";

  //while(it2 != sorted.end()){
  //  cout << (*it).first << endl;
  //  it2++;
  //}
  
  while(it != org.end()){
  
    key = (*it).first;
  
    //cout << "key" << key << endl;
    
    if(prevkey != key){
      //cout << "find" << key << endl;
      it2 = sorted.find(key);
    }
  
    //cout << (*it).second << " " << (*it2).second <<endl;
    
    if((*it).second != (*it2).second){
      return false;
    }
  
  
    
    prevkey = key;
    it++;
    it2++;
  
  }
  
  //vector<string>::iterator it;
  //it = sortCard.begin();
  //string key,prevkey,key2,c1,c2;
  //map<string,string>::iterator it2;
  //pair<string,string> p;
  //prevkey = "";
  //while(it != sortCard.end()){
  //  key = (*it).substr(1,1);
  //
  //  it2 = m.find(key);
  //
  //  while(it2 != m.end()){
  //
  //    p = *it2;
  //
  //    if(p.first != key){
  //      break;
  //    }
  //
  //    //
  //    c1 = (*it).substr(0,1);
  //    c2 = p.second;
  //    if(c1 != c2){
  //      cout << "false" << *it << p.second << p.first << "key" << key << endl;
  //      return false;
  //    }
  //    
  //    if((it+1) != sortCard.end()){
  //      if((*(it+1)).substr(1,1) == key){
  //        it++;
  //      }
  //    }
  //    
  //    it2++;
  //    
  //  }
  //  //if(key != prevkey){
  //  //  
  //  //}
  //
  //  prevkey = key;
  //  it++;
  //}
  
  return true;
  
}

int main(){
  long ii,jj,kk;
  vector<int> a;
  int n;
  vector<string> c,b,s;
  multimap<string,string>  seq;
  multimap<string,string>  bseq,sseq;
  string t1,t2,tmp;
  cin >> n;

  c.resize(n);
  b.resize(n);
  s.resize(n);
  
  for(ii=0;ii<n;ii++){
    cin >> c[ii];
    seq.insert(make_pair(c[ii].substr(1,1),c[ii].substr(0,1)));
  }
  //cout << "hoge" << endl;
  copy(c.begin(),c.end(),b.begin());
  copy(c.begin(),c.end(),s.begin());

  //bubble sort
  for(ii=0;ii<n;ii++){

    for(jj=n-1;jj>=ii+1;jj--){
      t1 = b[jj  ].substr(1,1);
      t2 = b[jj-1].substr(1,1);

      if(t1 < t2){
        tmp = b[jj];
        b[jj] = b[jj-1];
        b[jj-1] = tmp;
      }
      
    }
  }
  
  for(ii=0;ii<n;ii++){
    bseq.insert(make_pair(b[ii].substr(1,1),b[ii].substr(0,1)));
  }
  
  //selection sort
  int minj;

  for(ii=0;ii<n;ii++){

    minj = ii;

    for(jj=ii;jj<n;jj++){
      t1 = s[jj  ].substr(1,1);      
      t2 = s[minj].substr(1,1);      

      if(t1 < t2){
        minj = jj;
      }
      
    }

    //cout << "minj:" << minj << "t1:" << t1 << "t2:" << t2 << endl;
    tmp = s[ii];
    s[ii] = s[minj];
    s[minj] = tmp;
    
  }

  for(ii=0;ii<n;ii++){
    sseq.insert(make_pair(s[ii].substr(1,1),s[ii].substr(0,1)));
  }
  
  vector<string>::iterator it;

  it = b.begin();

  while(it != b.end()){
    cout << *it ;
    it++;
    if(it != b.end()){
      cout << " " ;
    }
  }
  cout << endl;

  if(isStable(seq,bseq)){
    cout << "Stable" << endl;
  }
  else{
    cout << "Not stable" << endl;
  }
  
  it = s.begin();
  while(it != s.end()){
    cout << *it ;
    it++;
    if(it != s.end()){
      cout << " " ;
    }
  }
  cout << endl;

  if(isStable(seq,sseq)){
    cout << "Stable" << endl;
  }
  else{
    cout << "Not stable" << endl;
  }
  
  return 0;
}



Measured memory_bytes: 3188