#include<stdio.h>
int sta(int * ,int *,int ,char *, char *);
void Bubble(char *,int *,int);
void Select(char *,int *,int ,int *,char *);
void inswap(int *, int *);
void chswap(char *,char*);
int main(){
  int i,j,num;
  int a[36],a1[36],a2[36];
  char c[36],c1[36],c2[36];

  scanf("%d",&num);

  for(i=0;i<num;i++) scanf(" %c%d",&c[i],&a[i]);
  for(i=0;i<num;i++){
    a1[i]=a[i];
    c1[i]=c[i];
    a2[i]=a[i];
    c2[i]=c[i];
  }
  Bubble(c,a,num);
  Select(c1,a1,num,a2,c2);
/*  j=sta(a,a1,num);
  if(j==-1) printf("Not stable\n");
  else printf("Stable\n");*/
  //  for(i=0;i<num;i++) printf("%c%d char_address : %p\n",c[i],a[i],&c[i]);
//  printf("\n");
  return 0;
}

void Bubble(char *c1,int *a1,int num){
int i,j;
  for(i=0;i<(num-1);i++){
    for(j=(num-1);j>i;j--){
      if(a1[j-1] > a1[j]){
   /*     tmp = a[j-1];
        a[j-1] = a[j];
        a[j] = tmp;
        step++; */
        inswap(&a1[j-1],&a1[j]);
        chswap(&c1[j-1],&c1[j]);
      }
    }
  }
  for(i = 0;i < num-1;i++) printf("%c%d ",c1[i],a1[i]);
  printf("%c%d",c1[num-1],a1[num-1]);
  printf("\n");
  printf("Stable\n");
}

void Select(char *c,int *a, int array_size,int *b,char *c1)
{
  int i; // ??????????????????????????????????????????
  int j,k; // ?????????????´????????????????????????????
  int min; // ????°?????????????????´??????????????????????
  int temp; // ????????¨??????????????°
  int step=0;

  for (i = 0; i < array_size-1; i++) {
    min = i; // ??????????????????????°???????????´???¨??????

    for (j = i+1; j < array_size; j++) { // ??????????????????

      if (a[j] < a[min]) {
        min = j; // ????°?????????????????´??????´??°
      }
    }
    //  for(k=0;k<array_size;k++){
    //    printf("%d ",a[k]);

    //  }
    //    printf("\n");
    // ????°?????????????????´?????????????????´???¨??????
    inswap(&a[i],&a[min]);
    chswap(&c[i],&c[min]);
    if(i!=min)    step++;
  }

  for (i = 0; i < array_size-1; i++) {
    printf("%c%d ",c[i], a[i]);
  }
  printf("%c%d\n",c[i],a[i]);
  j=sta(a,b,array_size,c,c1);
  if(j==-1) printf("Not stable\n");
  else printf("Stable\n");
  // i=sta(a,carray_size);
  //printf("%d\n",step);

}

void inswap(int *a,int *b){
  int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
void chswap(char *a,char *b){
  int tmp;
  tmp=*a;
  *a=*b;
  *b=tmp;
}

int sta(int *in,int *out,int num, char *m,char *m1){
  int i,j,a,b;
  for(i=0;i<=num-1;i++){
    for(j=i+1;j<=num-1;j++){
      for(a=0;a<=num-1;a++){
        for(b=a+1;b<=num-1;b++){
          if(m[i] == m1[i] && in[i]==in[j] && in[i]==out[b] && in[j]==out[a]) return -1;
        }
      }
    }
  }
  return 1;
}