#include<stdio.h>

#define M 36



typedef struct{
  char mark;
  int value;
} Data;

  Data A[M],B[M];



void Bubblesort(Data *C,int N){
  
  int i,j;
  Data k;
  
  for(i=0;i<N;i++){
    for(j=N-1;j>i;j--){
      if(C[j].value < C[j-1].value){
	k = C[j];
	C[j] = C[j-1];
	C[j-1] = k;
      }
    }
  }
}

void SelectionSort(Data *C, int N){

  int i,j,minj;
  Data k;
  
  for(i=0;i<N;i++){
    minj = i;
    for(j=i;j<N;j++){
      if(C[j].value < C[minj].value) minj = j;
    }

    k = C[i];
    C[i] = C[minj];
    C[minj] = k;
  }

}

int isStable(Data *A,Data *B,int n)
{
  int i;
  for(i=0;i<n;i++)
    {
      if(A[i].mark != B[i].mark)return 0;
    }
  return 1;
}


int main(){

  int i,j,k,x,y;
  char s[2];
  Data A[M],B[M];

  scanf("%d",&k);

  for(i=0;i<k;i++){
    scanf("%d",s);
    A[i].mark = s[0];
    A[i].value = s[1];
    B[i] = A[i];
  }

  Bubblesort(A,k);
  SelectionSort(B,k);
  
  for(i=0;i<k;i++)
    {
      s[0] =A[i].mark;
      s[1]=A[i].value;
 
      if(i==k-1) printf("%s\n",s);
      else printf("%s ",s);
    }
  s[0] = A[i].mark;
  s[1]=A[i].value;
  printf("%s\n",s);
  printf("Stable\n");
 
  for(i=0;i<k;i++)
    {
      s[0] = B[i].mark;
      s[1]=B[i].value;

      if(i==k-1) printf("%s\n",s);
      else printf("%s ",s);
    }

  if(isStable(A,B,k) == 1)
    {
      printf("Stable\n");
    }
  else{
    printf("Not stable\n");
  }
 
 
  return 0;
}

