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

#define MAX 36

int main(){

  int i, j, a, b, num, min, ans1, ans2;
  int temp[MAX];

  char oridata[MAX][3];
  char data1[MAX][3];
  char data2[MAX][3];

  ans1 = 0;
  ans2 = 0;

  scanf("%d", &num);

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

    scanf("%s", &oridata[i]);

    data1[i][0] = oridata[i][0];
    data1[i][1] = oridata[i][1];
    data1[i][2]='\0';
    data2[i][0] = oridata[i][0];
    data2[i][1] = oridata[i][1];
    data2[i][2]='\0';
  }

  
  //バブルソート
  for(i = 0; i < num - 1; i++){

    for(j = num - 1; j > i; j--){

      if(data1[j][1] < data1[j - 1][1]){
	
	temp[0] = data1[j - 1][0];
	temp[1] = data1[j - 1][1];

	data1[j - 1][0] =  data1[j][0];
	data1[j - 1][1] =  data1[j][1];

	data1[j][0] = temp[0];
	data1[j][1] = temp[1];
	
      }
	
    }

  }

  //選択ソート
  for(i = 0; i < num - 1; i++){

    min = i;

    for(j = i + 1; j < num; j++){

      if(data2[min][1] > data2[j][1]){
	
	min = j;
	
      }
	
    }


    if(data2[i][1] != data2[min][1]){

      temp[0] = data2[min][0];
      temp[1] = data2[min][1];

      data2[min][0] =  data2[i][0];
      data2[min][1] =  data2[i][1];

      data2[i][0] = temp[0];
      data2[i][1] = temp[1];

    }
     
  }



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

    for(j = i + 1; j < num; j++){

      for(a = 0; a < num; a++){

	for(b = a + 1; b < num; b++){

	  if(oridata[i][1] == oridata[j][1] && (strcmp(oridata[i],data1[b])==0) && (strcmp(oridata[j],data1[a])==0))
	    ans1 = 1;

	}	

      }

    }

  }

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

    for(j = i + 1; j < num; j++){

      for(a = 0; a < num; a++){

	for(b = a + 1; b < num; b++){

	  if(oridata[i][1] == oridata[j][1] && (strcmp(oridata[i],data2[b])==0) &&( strcmp(oridata[j],data2[a])==0)) 
	    ans2 = 1;

	}	

      }

    }

  }



  //出力
  for(i = 0; i < num; i++){

    printf("%c%c ", data1[i][0],data1[i][1]);

  }
   
  if(ans1 == 0)
    printf("\nStable\n");
  else
    printf("\nNot stable\n");


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

    printf("%c%c ", data2[i][0],data2[i][1]);

  }

  if(ans2 == 0)
    printf("\nStable\n");
  else
    printf("\nNot stable\n");

  return 0;

}