#include<stdio.h>
#include<string.h>
# define N 36
int main(){
  int i, j, n;
  int mini;
  char A1[N];
  char A2[N];
  int N1[N];
  int N2[2];
  int stability =1;//0:not stable 1:stable
  int tmp1;
  char tmp2;

  scanf("%d",&n);
  for( i=0; i<n; i++ ){//Scan Input
    scanf(" %c%d",&A1[i],&N1[i]);
    A2[i]=A1[i];
    N2[i]=N1[i];
  }
  for( i=0; i<n; i++ ){//Bubble Sort
    for( j=n-1; j>=i+1; j-- ){
      if( N1[j]<N1[j-1]){
    tmp1=N1[j];
    N1[j]=N1[j-1];
    N1[j-1]=tmp1;
    tmp2=A1[j];
    A1[j]=A1[j-1];
    A1[j-1]=tmp2;
      }
    }
  }


  for( i=0; i<n; i++ ){//Selection Sort
    mini = i;
    for( j=i; j<n ; j++ ){
      if( N2[j] < N2[mini] ){
    mini = j;
      }    
    }
    tmp1=N2[i];
    N2[i]=N2[mini];
    N2[mini]=tmp1;
    tmp2=A2[i];
    A2[i]=A2[mini];
    A2[mini]=tmp2;
  }
 
 
  for( i=0; i<n; i++ ){
    //bubble sort  
    printf("%c%d", A1[i],N1[i]);
    if( i<n-1 ) printf(" ");
  }

  printf("\nStable\n");

 
  for( i=0; i<n; i++ ){
    //selection sort
    printf("%c%d", A1[i],N1[i]);
    if( i<n-1 ) printf(" ");
  }
  
  for( i=0; i<n; i++ ){
		if( N1[i]==N2[i] ){
			if(A1[i]!=A2[i]){
				stability = 0;
				break;
			}
		}
  }
  if( stability == 1 ) printf("\nStable\n");
  else printf("\nNot stable\n");
 

  return 0;
}