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

int main(){
  int n, i, j, flag=1;
  char a[36][3], b[36][3], c[36][3], d[3], e[3];
  scanf("%d", &n);
  for(i=0; i<n; i++){
    scanf("%s", a[i]);
    strcpy(b[i], a[i]);
    strcpy(c[i], a[i]);
  }

  //バブルソート
  while(flag==1){
    flag=0;
    for(i=n-1; i>0; i--){
      if(b[i][1] < b[i-1][1]){
	strcpy(d, b[i]);
	strcpy(b[i], b[i-1]);
	strcpy(b[i-1], d);
	flag=1;
      }
    }
  }

  for(i=0; i<n-1; i++){
    printf("%s ",b[i]);
  }
  printf("%s\n", b[n-1]);

  //選択ソート

  for(i=0; i<n-1; i++){
    strcpy(e, c[i]);
    for(j=1; j<n; j++){
      if(c[j][1]<e[1]){
	strcpy(e, c[j]);
      }
    }
    strcpy(d, c[i]);
    strcpy(c[i], e);
    strcpy(e, d);
  }

  for(i=0; i<n-1; i++){
    printf("%s ", c[i]);
  }
  printf("%s\n", c[n-1]);
  
  return 0;
}

