#include <stdio.h>

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

   scanf("%d", &N);

   int C1[N], C2[N], D1[N], D2[N];

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

   for(i = 0; i < N; i++) {
      D1[N] = C1[N];
      D2[N] = C2[N];
   }

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

            y = C2[j];
            C2[j] = C2[j - 1];
            C2[j - 1] = y;
         }
      }
   }

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

            y = D2[i];
            D2[i] = D2[minj];
            D2[minj] = y;
      }
   }


   for(i = 0; i < N; i++) {
      g1 = 1;
      if (C1[i] != D1[i]||C2[i] != D2[i]) {
         g1 = 2;
      }
   }

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

   printf("Stable\n");

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

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

   return 0;
}
