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

int isstable(int*, int*, int);

int main(){
  int i, j, p, n, min;
  int A[36], B[36], b[36];
  char q;
  char C[36], c1[36], c2[36];

  scanf("%d",&n);
  
  for(i=0 ; i<n ; i++) scanf("%c%d",&C[i],&A[i]);

  B = A;
  strcpy(C,c1);
  
  for(i=0 ; i<n ; i++){
    for(j=n-1 ; j>i ; j--){
      if(B[j] < B[j-1]){
	p = B[j];
	B[j] = B[j-1];
	B[j-1] = p;

	q = c1[j];
	c1[j] = c1[j-1];
	c1[j-1] = q;
      }
    }
  }
  
  for(i=0 ; i<n-1 ; i++) printf("%c%d ",c1[i],B[i]);
  printf("%c%d\n",c1[i],B[i]);

  if(isstable(A,B,n)) printf("Stable\n");
  else printf("Not stable");

  b = A;
  strcpy(C,c2);
  
  for(i=0 ; i<n ; i++){
    min = i;
    for(j=i ; j<n ; j++){
      if(b[j] < b[min]) min = j;
    }
    p = b[j];
    b[j] = b[j-1];
    b[j-1] = p;
    
    q = c2[j];
    c2[j] = c2[j-1];
    c2[j-1] = q;
  }
  
  for(i=0 ; i<n-1 ; i++) printf("%c%d ",c2[i],b[i]);
  printf("%c%d\n",c2[i],b[i]);
  
  if(isstable(A,B,n)) printf("Stable\n");
  else printf("Not stable");
  

  return 0;
}

int isstable(int* in, int* out, 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] == in[j] && in[i] == out[b] && in[j] == out[a]) return 0;
  return 1;
}