#include<stdio.h>

void BubbleSort(int );
void SelectionSort(int);

struct card{

  char character;   

  int  number;

};


struct card inputdata[100];
struct card inputdata2[100];

int main(){

  int sumcard,i,j,flag;

  flag = 0;

  scanf("%d",&sumcard);

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

    scanf("%c%c%d",&inputdata[i].character,&inputdata[i].character,&inputdata[i].number);
    // scanf("%c",&inputdata[i].number[0]);

    inputdata2[i].character = inputdata[i].character;
    inputdata2[i].number = inputdata[i].number;

  }

  /* printf("\n");

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

    printf("%c %d\n",inputdata[i].character,inputdata[i].number);

    }*/

  //  printf("test\n");
  BubbleSort(sumcard);

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

    printf("%c%d ",inputdata[i].character,inputdata[i].number);

  }

  printf("\n");

  printf("Stable\n");

  
  SelectionSort(sumcard);

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

    printf("%c%d ",inputdata2[i].character,inputdata2[i].number);

  }

  printf("\n");

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

    if(inputdata[i].character != inputdata2[i].character){

      flag = 1;

      break;

    }

  }

  if(flag == 0){

    printf("Stable\n");

  }

  else{

    printf("Not Stable\n");

  }


  return 0;

}

void BubbleSort(int sumcard){

  int i,x,j;
   char y;

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

    for(j = sumcard-1; j >= i+1; j--){

      if(inputdata[j].number < inputdata[j-1].number){

	x = inputdata[j].number;
	y = inputdata[j].character;

	inputdata[j].number =  inputdata[j-1].number;
	inputdata[j].character = inputdata[j-1].character;

	inputdata[j-1].number = x;
	inputdata[j-1].character = y;

      }
    }

  }
}

void SelectionSort(int sumcard){

  int i,j,minj,x;
  char y;

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

    minj = i;

    for(j = i; j < sumcard; j++){

      if(inputdata2[j].number < inputdata2[minj].number){

	minj = j;

      }

      x = inputdata2[i].number;
      y = inputdata2[i].character;

      inputdata2[i].number = inputdata2[minj].number;
      inputdata2[i].character = inputdata2[minj].character;

      inputdata2[minj].number = x;
      inputdata2[minj].character = y;

    }

  }

}

 