#include <stdio.h>
#include <string.h>
typedef struct {
  char value[3]; //null分の配列も用意
}SCHD;
int main(){
  SCHD card[36];
  SCHD extcard[36];
  char str[3];
  int n,i,j;
  int min;
  scanf("%d",&n);
  for(i=0;i<n;i++){   
    scanf("%s",card[i].value);
    strcpy(extcard[i].value,card[i].value);   
  }
  //strcmp A,B -> +
  for(i=0;i<n;i++){
    for(j=n-1;j>i;j--){
      if(card[j].value[1]<card[j-1].value[1]){
	strcpy(str,card[j].value);
	strcpy(card[j].value,card[j-1].value);
	strcpy(card[j-1].value,str);
      }     
    }
  }
  for(i=0;i<n;i++){
    printf("%s ",card[i].value);
  }
  printf("\n"); //bubble sort

  for(i=0;i<n-1;i++){
    min=i;
    for(j=i;j<n;j++){
      if(extcard[j].value[1]<extcard[min].value[1])min=j;
  }
	strcpy(str,extcard[i].value);
	strcpy(extcard[i].value,extcard[min].value);
	strcpy(extcard[min].value,str);
  }
  for(i=0;i<n;i++){
    printf("%s ",extcard[i].value);
  }
  printf("\n"); //selection sort
    return 0;
}

