#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;

int main() {
 int n;
    cin >> n;
    vector<string> c(n);
    
  rep(i,n) {
   cin >> c[i];
  }
   
    
   vector<string> d(n);
    rep(i,n) {
     d[i] = c[i];
    }
    
   
    
    for(int i = 0; i< n; i++) {
      for(int j =  n-1; j > i ; j--){
          if((int)c[j].at(1) < (int)c[j-1].at(1)) {
           swap(c[j],c[j-1]);
          }
      }
    }
       
    rep(i,n-1) {
         cout << c[i] << ' ';
    }
    cout << c[n-1] << endl;
    cout << "Stable" << endl;
    
    
    
    for(int i = 0; i<n; i++) {
     int minj = i;
    for(int j = i; j < n; j++){
     if((int)d[j].at(1) < (int)d[minj].at(1)) {
      minj = j;
     }
    }
        
    swap(d[i],d[minj]);
    }
          
    bool stable = true;
    rep(i,n) {
     if(c[i] != d[i]){
      stable = false;
     }
    }
    rep(i,n-1) {
         cout << d[i] << ' ';
    }
    cout << d[n-1] << endl;
    if(stable) {
     cout << "Stable" << endl;
    } else {
     cout << "Not stable" << endl;
    }
       
}
