#include <stdio.h>

#define N 100

#define true 1
#define false 0

typedef struct{
  char x[N];
}array;

int n;
array in[N];

void BubbleSort(array *);
void SelectionSort(array *);
int isStable(array *);
int main(){
  int i, j;
  array A[N],B[N];

  scanf("%d",&n);

  for(i=1;i<=n;i++){
    scanf("%s", in[i].x);
   B[i] = A[i]=in[i];
  }

  BubbleSort(A);
  SelectionSort(B);

  return 0;
}

void BubbleSort(array *A){
  int i,j;
  array swap;

  for(i=1;i<n;i++)
    for(j=n;j>i;j--)
      if(A[j].x[1]<A[j-1].x[1]){
	swap = A[j];
	A[j] = A[j-1];
	A[j-1] = swap;
      }

  printf("%s",A[0].x);
  for(i=1;i<=n;i++){
    printf("%s", A[i].x);
    if(i!=n)printf(" ");
  }
  printf("\n");

  if(isStable(A)) printf("Stable\n");
  else printf("Not stable\n");
}

void SelectionSort(array *B){
  int i,j,mini;
  array swap;

  for(i=1;i<=n-1;i++){
    mini = i;
    for(j=i+1;j<=n;j++)
      if(B[mini].x[1]>B[j].x[1]) mini = j;
    if(mini != i){
	swap = B[i];
	B[i] = B[mini];
	B[mini] = swap;
    }
  }

  printf("%s",B[0].x);
  for(i=1;i<=n;i++){
    printf("%s", B[i].x);
    if(i!=n)printf(" ");
  }

  printf("\n");

  if(isStable(B)) printf("Stable\n");
  else printf("Not stable\n");
}

int isStable(array *out){

  int i,j,a,b;

  for(i = 1;i< n;i++)
    for(j = i+1;j<= n;j++)
      for(a = 1; a<n; a++)
	for(b = a+1; b <= n;b++)
	  if(in[i].x[1]== in[j].x[1] && in[i].x[0] == out[b].x[0] && in[j].x[0] == out[a].x[0])  return false;

  return true;
 

}