#include <bits/stdc++.h>
using namespace std;
#define rep(i, a) for(int i=0; i<(int)(a); i++)
typedef long long ll;
const int inf = 1001001001;

int main()
{
  int n; cin >> n;
  vector<char> c(n);
  vector<int> a(n);
  rep(i, n) {
    string s; cin >> s;
    c[i] = s[0];
    a[i] = s[1]-'0';
  }

  vector<char> c1 = c;
  vector<int> a1 = a;
  for (int i=0; i<n; i++) {
    for (int j=n-1; j>=i+1; j--) {
      if (a1[j] < a1[j-1]) {
        swap(a1[j], a1[j-1]);
        swap(c1[j], c1[j-1]);
      }
    }
  }
  rep(i, n) {
    if (i > 0) cout << " ";
    cout << c1[i] << a1[i];
  }
  cout << endl << "Stable" << endl;

  vector<char> c2 = c;
  vector<int> a2 = a;
  for (int i=0; i<n; i++) {
    int minj = i;
    for (int j=i; j<n; j++) {
      if (a2[j] < a2[minj]) minj = j;
    }
    swap(a2[i], a2[minj]);
    swap(c2[i], c2[minj]);
  }
  rep(i, n) {
    if (i > 0) cout << " ";
    cout << c2[i] << a2[i];
  }
  cout << endl;
  if (c1==c2&&a1==a2) cout << "Stable" << endl;
  else cout << "Not stable" << endl;

  return 0;
}

