#include <stdio.h>

int main() {
  int n;
  int i,j,e;
  int a[101],b[101];
  int t,minj,flag;
  char c[101],kara,m,d[101],f[4];
  int sta = 0;
  scanf("%d", &n);
  scanf("%c",&kara);
  e = 0;
  for(i=0; i<n; i++) {

    scanf("%c %d",&c[i],&a[i]);
    scanf("%c",&kara);

    //    printf("%c %d\n",c[i],a[i]);
    b[i] = a[i];
    d[i] = c[i];

  }



  //Bubble Sort

  for(i = 0; i<=n-1;i++) {
    for(j = 0; j<=n-1;j++) {

      if(a[j] < a[j-1]) {

	t = a[j];
	a[j] = a[j-1];
	a[j-1] = t;

	m = c[j];
	c[j] = c[j-1];
	c[j-1] = m;
      }
    }
  }

  for(i = 0;i<n;i++) {

    printf("%c%d",c[i],a[i]);
    
    if(i != n-1) printf(" ");

  }

  printf("\nStable\n");




  // Selsection Sort

  for(i = 0; i<=n-1; i++) {
    minj = i;
    flag = 0;
  
    for(j = i; j<=n-1;j++) {
      if(b[j] < b[minj]) {
	//	printf("%d < %d\n",b[j],b[minj]);
	minj = j;
	//printf("minj = %d\n",b[minj]);
	flag = 1;
      }
    }

    

    if(flag == 1) {

      t = b[i];
      b[i] = b[minj];
      b[minj] = t;

      m = d[i];
      d[i] = d[minj];
      d[minj] = d[i];
  
    }
  }

   
  for(i=0;i<n;i++) {
     printf("%c%d",d[i],b[i]);
    if(n != n-1) {
      printf(" ");
    }

  }


printf("\n");
flag = 0;
for(j=0;j<n;j++){

  if(c[i] != d[i]) flag = 1;
 } 

if(flag == 1) printf("Not stable\n");
 else printf("Stable\n");

}