/*
    問題をよく読もう！
    論理的に考えよう！
    サンプルを確認しよう!
    絶対に諦めるな！
    工夫をしろ！
    配列は少し多めにとっておく

    Twitterは終わるまでログアウト！
    （間違えて解法をツイートしてはいけないから）

*/
//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<stdio.h>
#include<cstring>
//namespace
using namespace std;
//繰り返し
#define REP(i, m, n) for(int i=(int)m; i<(int)n; ++i)
#define rep(i, n) REP(i, 0, n)
//イテレータ
#define all_range(C) begin(C), end(C)
//簡略化
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
typedef pair<string,int> pst;

const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
//最大最小
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) {if(a>b) a=b;}
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) {if(a<b) a=b;}

//関数

//最大公約数を求める
ll my_gcd(ll x, ll y) {
  ll r;

  while(y!=0) {
    r = x%y;
    x = y;
    y = r;
  }

  return x;
}

//最小公約数を求める
ll my_lcm(ll x, ll y) {

  return (x*y)/my_gcd(x,y);
}

//xのy乗を求める ※参考：10^18乗まで
ll my_pow(ll x, ll y) {
  ll sum = 1;

  while(y>0) {
    sum *= x;
    --y;
  }

  return sum;
}

/*考えを書くスペース

*/
//main.cpp----------------------------
#define MAX 36

struct Card {
  char mark;
  int number;
};

void bubblesort(struct Card C[], int N) {

  for(int i=0; i<N-1; ++i) {
    for(int j=N-1; j>i; --j) {
      if(C[j].number<C[j-1].number) {
        swap(C[j].number, C[j-1].number);
        swap(C[j].mark, C[j-1].mark);
      }
    }
  }
}

void selectionsort(struct Card C[], int N) {

  int minj;
  for(int i=0; i<N-1; ++i) {
    minj = i;
    for(int j = i; j<N; ++j) {
      if(C[j].number<C[minj].number)
        minj = j;
    }
    swap(C[i].number, C[minj].number);
    swap(C[i].mark, C[minj].mark);
  }
}

bool isStable(struct Card in[], struct Card out[], int N) {

  for(int i=0; i<N-1; ++i) {
    for(int j=i+1; j<N-1; ++j) {
      for(int a=0; a<N-1; ++a) {
        for(int b=a+1; b<N-1; ++b) {
          if(in[i].number==in[j].number&&in[i].number==out[b].number&&in[j].number==out[a].number) {
            return false;
          }
        }
      }
    }
  }

  return true;
}

int main() {
  int n;
  struct Card B[MAX+1];
  struct Card I[MAX+1];

  cin >> n;

  rep(i, n) {
    cin >> B[i].mark >> B[i].number;
    I[i].mark = B[i].mark;
    I[i].number = B[i].number;
  }

  bubblesort(B, n);

  rep(i, n) {
    cout << B[i].mark << B[i].number;
    if(i==n-1) cout << endl;
    else cout << " ";
  }
  cout << "Stable" << endl;

  selectionsort(I, n);

  rep(i, n) {
    cout << I[i].mark << I[i].number;
    if(i==n-1) cout << endl;
    else cout << " ";
  }

  if(isStable(B, I, n)) cout << "Stable" << endl;
  else cout << "Not stable" << endl;


  return 0;
}

