#include<stdio.h>

struct Card{
   char mark;
   char num;
};

int main () {

   struct Card c1[36], c2[36], c3;
   int n, i, j, minj, check = 0;
   char ch;

   scanf("%d%c",&n, &ch);

   for(i = 0; i < n; i++){
      scanf("%c%c%c", &c1[i].mark, &c1[i].num, &ch);
   }


   for(i = 0; i < n; i++){
      c2[i] = c1[i];
   }



   for(i = 0; i <= n-1; i++){
      for(j = n-1; j >=i+1; j--){
         if(c1[j].num < c1[j-1].num){
            c3 = c1[j];
            c1[j] = c1[j-1];
            c1[j-1] = c3;
         }
      }
   }


   for(i = 0; i <= n-1; i++){
      minj = i;
      for(j = i; j <= n-1; j++){
         if(c2[j].num < c2[minj].num){
            minj = j;
         }
      }
      if(minj != i){
         c3 = c2[j];
         c2[j] = c2[minj];
         c2[minj] = c3;
      }
   }



   for(i = 0; i < n; i++){
      if(i)
         printf(" ");
      printf("%c%c", c1[i].mark, c1[i].num);
   }
   printf("\nStable\n");


   for(i = 0; i < n; i++){
      if(i)
         printf(" ");
      printf("%c%c", c2[i].mark, c2[i].num);
      if(c1[i].mark == c2[i].mark)
         check++;
   }


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

   return 0;
}