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

/*char card[40][3], card_i[40][3];

void BubbleSort(int n);
void SelectionSort(int n);
void write(int n);
void stable(int n);

int main(void){
  int n, i, j;

  scanf("%d", &n);
  for(i = 0; i < n; i++){
    scanf("%s", card[i]);
    strcpy(card_i[i], card[i]);
  }
  
  BubbleSort(n);
  stable(n);
  SelectionSort(n);
  stable(n);

  return 0;
}

void BubbleSort(int n){
  char k, l;
  int i, j;
  for(i = 0; i < n-1; i++){
    for(j = n-1; j > i; j--){
      if(card_i[j][1] < card_i[j-1][1]){
	k = card_i[j][1];
	l = card_i[j][0];
	card_i[j][1] = card_i[j-1][1];
	card_i[j][0] = card_i[j-1][0];
	card_i[j-1][1] = k;
	card_i[j-1][0] = l;
      }
    }
  }
  write(n);
  return;
}


void SelectionSort(int n){
  int i, j, minj;
  char k, l;

  for(i = 0; i < n-1; i++){
    minj = i;
    for(j = i; j < n-1; j++){
      if(card_i[j][1] < card_i[minj][1]) minj = j;
    }
    write(n);
    k = card_i[minj][1];
    l = card_i[minj][0];
    card_i[minj][1] = card_i[i][1];
    card_i[minj][0] = card_i[i][0];
    card_i[i][1] = k;
    card_i[i][0] = l;
  }
  write(n);
  return;
}

void write(int n){
  int i, j;
  for(i = 0; i < n; i++){
    for(j = 0; j < 2; j++){
      printf("%c", card_i[i][j]);
    }
    printf(" ");
  }
  printf("\b\n");
  return;
}

void stable(int n){
  int i, j, k[4], kk[4], co1 = 0, co2 = 0, co = 0, z;
  for(i = 0; i < 9; i++){
      for(j = 0; j < n; j++){
	if(card_i[j][1] == 49+i){
	  k[co1] = card_i[j][0];
	  co1++;
	  co++;
	}
      }
      for(j = 0; j < n; j++){
	if(card[j][1] == 49+i){
	  kk[co2] = card[j][0];
	  co2++;
	}
      }
      for(j = 0; j < co; j++){
	if(co == 0) break;
	if(k[j] != kk[j]){
	  for(z = 0; z < n; z++){
	    strcpy(card_i[z], card[z]);
	  }
	  printf("Not stable\n");
	  return;
	}
      }
      co1 = 0;
      co2 = 0;
      co = 0;
  }
  for(z = 0; z < n; z++){
    strcpy(card_i[z], card[z]);
  }
  printf("Stable\n");
  return;
}
*/

struct card{
  int num;
  char mark;
};

void BubbleSort(int n);
void SelectionSort(int n);
void write(int n);
void stable(int n);

int main(void){
  int n, i, j;

  struct card card_i[40], card_j[40];

  scanf("%d", &n);
  for(i = 0; i < n; i++){
    scanf("%c%d", card[i].mark, card[i].num);
    strcpy(card_i[i].num, card[i].mark);
    card_i[i].num = card[i].num;
  }

  BubbleSort(n);
  stable(n);
  SelectionSort(n);
  stable(n);

  return 0;
}

void BubbleSort(int n){
  char l;
  int i, j, k;
  for(i = 0; i < n-1; i++){
    for(j = n-1; j > i; j--){
      if(card_i[j].num < card_i[j-1].num){
	k = card_i[j].num;
	l = card_i[j].mark;
	card_i[j].num = card_i[j-1].num;
	card_i[j].mark = card_i[j-1].mark;
	card_i[j-1].num = k;
	card_i[j-1].mark = l;
      }
    }
  }
  write(n);
  return;
}

void SelectionSort(int n){
  int i, j, minj, k;
  char l;

  for(i = 0; i < n-1; i++){
    minj = i;
    for(j = i; j < n-1; j++){
      if(card_i[j].num < card_i[minj].num) minj = j;
    }
    k = card_i[minj].num;
    l = card_i[minj].mark;
    card_i[minj].num = card_i[i].num;
    card_i[minj].mark = card_i[i].mark;
    card_i[i].num = k;
    card_i[i].mark = l;
  }
  write(n);
  return;
}

void write(int n){
  int i, j;
  for(i = 0; i < n; i++){
    printf("%c%d ", card_i[i].mark, card_i[i].num);
  }
  printf("\b\n");
  return;
}

void stable(int n){
  int i, j, k[4], kk[4], co1 = 0, co2 = 0, co = 0, z;
  for(i = 0; i < 9; i++){
      for(j = 0; j < n; j++){
	if(card_i[j].num == 49+i){
	  k[co1] = card_i[j].mark;
	  co1++;
	  co++;
	}
      }
      for(j = 0; j < n; j++){
	if(card[j].num == 49+i){
	  kk[co2] = card[j].mark;
	  co2++;
	}
      }
      for(j = 0; j < co; j++){
	if(co == 0) break;
	if(k[j] != kk[j]){
	  for(z = 0; z < n; z++){
	    card_i[z].mark = card[z].mark;
	  }
	  printf("Not stable\n");
	  return;
	}
      }
      co1 = 0;
      co2 = 0;
      co = 0;
  }
  for(z = 0; z < n; z++){
    card_i[z].mark = card[z].mark;
  }
  printf("Stable\n");
  return;
}