#include <stdio.h>
#include <stdlib.h>

void BubbleSort(char hoge[36][2],int);
void SelectionSort(char hoge[36][2],int);

int main(){
  int N,i,j,n,flag=0;
  char A[36][2],a[36][2];
  scanf("%d",&N);
  for(i=0;i<N;i++)
    scanf("%s",A[i]);
  for(i=0;i<N;i++){
    a[i][0]=A[i][0];
    a[i][1]=A[i][1];
  }
  BubbleSort(A,N);
  SelectionSort(a,N);
  for(i=0;i<N;i++){
    printf("%c%c",a[i][0],a[i][1]);
    if(i<N-1)
      printf(" ");
  }
  printf("\n");
  for(i=0;i<N;i++)
    if(A[i][0]!=a[i][0])
      flag=1;
  if(flag==1)
    printf("Not stable\n");
  else
    printf("Stable\n");
  return 0;
}

void BubbleSort(char A[32][2],int N){
  int i,j,B[32],n;
  char keep[2];
  for(i=0;i<N;i++)
    B[i]=A[i][1]-48;
  for(j=0;j<N;j++){
    for(i=N-1;i>0;i--){
      if(B[i]<B[i-1]){
	n=B[i];
	B[i]=B[i-1];
	B[i-1]=n;
	keep[0]=A[i][0];
	A[i][0]=A[i-1][0];
	A[i-1][0]=keep[0];
	keep[1]=A[i][1];
	A[i][1]=A[i-1][1];
	A[i-1][1]=keep[1];
      }
    }
  }
  for(i=0;i<N;i++){
    printf("%c%c",A[i][0],A[i][1]);
    if(i<N-1)
      printf(" ");
  }
  printf("\n");
  printf("Stable\n");
    }

void SelectionSort(char A[32][2],int N){
  int i,j,B[32],n,minj;
  char keep[2];
  for(i=0;i<N;i++)
    B[i]=A[i][1]-48;
  for(i=0;i<N;i++){
    minj=i;
    for(j=i;j<N;j++){
      if(B[j]<B[minj]){
	minj=j;
      }
    }
    if(i!=minj){
      n=B[i];
      B[i]=B[minj];
      B[minj]=n;
      keep[0]=A[i][0];
      A[i][0]=A[minj][0];
      A[minj][0]=keep[0];
      keep[1]=A[i][1];
      A[i][1]=A[minj][1];
      A[minj][1]=keep[1];
    }
  }
}