#include <stdio.h>
void Bubblesort(char[36][3], int);
void SelectionSort(char[36][3], int);
int isStable(char[36][3], char[36][3], int);

int main() {

  char A[36][3],B[36][3],x;
  int i,j,k,N;

  scanf("%d",&N);

  for(i = 0; i < N; i++) {
  scanf("%s",A[i]);
  }
  for(i = 0 ; i < 3; i++) {
    for(j = 0; j < N; j++) {
      B[j][i] = A[j][i];
    }
  }
  Bubblesort(A,N);
  SelectionSort(B,N);
  return 0;
}


//??????????????????
void Bubblesort(char A[][3], int N) {
  int i,j,k;
  char x,B[36][3];
  for(i = 0 ; i < 3; i++) {
    for(j = 0; j < N; j++) {
      B[j][i] = A[j][i];
    }
  }
  
  for(i = 0; i < N-1; i++) {
    for(j = N-1; j > i; j--) {
      if(A[j][1] < A[j-1][1]) {
	for(k = 0; k < 2; k++) {
	  x = A[j][k];
	  A[j][k] = A[j-1][k];
	  A[j-1][k] = x;
	}
      }
    }
  }
 
  for(i = 0; i < N; i++) {
    printf("%s",A[i]);
    if(N-1 != i) printf(" ");
  }
  printf("\n");
  if(0 == isStable(B,A,N)) printf("Not stable\n");
  else printf("Stable\n");
  return;
}


//?????¬????????§????????????
void SelectionSort(char A[][3], int N) {
  int i,j,flag,minj;
  char x,B[36][3];
   for(i = 0 ; i < 3; i++) {
    for(j = 0; j < N; j++) {
      B[j][i] = A[j][i];
    }
  }

  for(i = 0; i < N; i++) {
    minj = i;
    flag = 0;
    for(j = i; j < N; j++) {
      if(A[j][1] < A[minj][1]) {
	minj = j; /*????°????????????£??????????????????????¨???¶?????????????????????*/
	flag = 1; /*for?????§?¢??????????????????§???????°???????????????£??????flag???1????????????*/
	
      }
    }
    if(flag == 1) {
      for(j = 0; j < 2; j++) {
      x = A[i][j];
      A[i][j] = A[minj][j];
      A[minj][j] = x;
    }
  }
  }
    for(i = 0; i < N; i++) {
      printf("%s",A[i]);
      if(N-1 != i) printf(" ");
    }
    printf("\n"); 
    if(0 == isStable(B,A,N)) printf("Not stable\n");
  else printf("Stable\n");
  return;
}

int isStable(char in[][3], char out[][3], int N) {
  int i,j,a,b;
  for(i = 0; i < N; i++) {
    for(j = i+1; j < N; j++) {
      for(a = 0; a < N; a++) {
	for(b = a+1; b < N; b++) {
	  if(in[i][1] == in[j][1] && in[i][0] == out[b][0] && in[j][0] == out[a][0]) return 0;
	}
      }
    }
  }
  return 1;
}