#include <stdio.h>

int main(void){
   int N, i, j, k, x, m, h, y, minj, g1, g2;

   scanf("%d", &N);

   int A[N], B[N], C1[N], C2[N], D1[N], D2[N], K1[N], K2[N], L1[N], L2[N];

   for(i = 0; i < N; i++) {
      scanf("%d", &A[i]);
   }
   for(i = 0; i < N; i++) {
      C1[N] = A[N];
   }

   for(i = 0; i < N; i++) {
      D1[N] = A[N];
   }

   for(i = 0; i < N; i++) {
      for(j = N - 1; j > i; i--) {
         if (C1[j] < C1[j - 1]) {
            x = C1[j];
            C1[j] = C1[j - 1];
            C1[j - 1] = x;
         }
      }
   }

   for(i = 0; i < N; i++) {
      minj = i;
      for(j = i; j < N; j++) {
         if (D1[j] < D1[minj]) {
            minj = j;
         }
      }
      if (minj != i) {
            x = D1[i];
            D1[i] = D1[minj];
            D1[minj] = x;
      }
   }

   g1 = 1;
   g2 = 1;


   for(i = 0; i < N; i++) {
      if (C1[i] != D1[i]) {
         g2 = 2;
      }
   }

   for(k = 0; k < N - 1; k++) {
      printf("%d ", C1[k]);
   }
   printf("%d\n", C1[N - 1]);

   if (g1 == 1) {
      printf("Stable\n");
   } else if (g1 == 2) {
      printf("Not stable\n");
   }

   for(k = 0; k < N - 1; k++) {
      printf("%d ", D1[k]);
   }
   printf("%d\n", D1[N - 1]);

   if (g2 == 1) {
      printf("Stable\n");
   } else if (g2 == 2) {
      printf("Not stable\n");
   }

   return 0;
}
