#include <iostream>
#include <string>

using namespace std;

int main(){
  int n, i, j, minj;
  bool flag = true, ns = false;
  string in1[36], in2[36], tmp;

  cin >> n;
  for(i = 0;i < n;++i){
    cin >> in1[i];
    in2[i] = in1[i];
  }

  //babble
  while(flag){
    flag = false;
    for(i = n - 1;i >= 1;--i){
      if(in1[i][1] < in1[i-1][1]){
	tmp = in1[i];
	in1[i] = in1[i-1];
	in1[i-1] = tmp;
	flag = true;
      }
    }
  }
  for(i = 0;i < n;++i){
    cout << in1[i];
    if(i != n-1)cout << " ";
  }
  cout << "\n";
  cout << "Stable" << endl;

  //select
  for(i = 0;i < n;++i){
    minj = i;
    for(j = i;j < n;++j){
      if(in2[j][1] < in2[minj][1])
	minj = j;
    }
    if(i != minj){
      tmp = in2[i];
      in2[i] = in2[minj];
      in2[minj] = tmp;
    }
  }
  for(i = 0;i < n;++i){
    cout << in2[i];
    if(i != n-1)cout << " ";
  }
  cout << "\n";
  for(i = 0; i < n;++i)
    if(in1[i] != in2[i])ns = true;
  if(ns)cout << "Not stable" << endl;
  else cout << "Stable" << endl;
  
  return 0;
}

