#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%d", &B[i], &A[i]);
   }
   for(i = 0; i < N; i++) {
      C1[N] = A[N];
      C2[N] = B[N];
   }

   for(i = 0; i < N; i++) {
      D1[N] = A[N];
      D2[N] = B[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;

            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 (D1[j] < D1[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;
      }
   }



   g1 = 1;
   for(i = 0; i < N; i++) {
      for(j = 1; j < 10; j++) {
         m = 0;
         if (C1[i] == j) {
            m++;
         }
         if (m > 1) {
            for(k = 0; k < N; k++) {
               h = 0;
               if (A[k] == j) {
                  K1[h] = B[k];
                  h++;
               }
            }

            for(k = 0; k < N; k++) {
               h = 0;
               if (C1[k] == j) {
                  K2[h] = C2[k];
                  h++;
               }
            }

            for(k = 0; k < N; k++) {
               if (K1[k] != K2[k]) {
                  g1 = 2;
               }
            }
         }
      }
   }

   g2 = 1;
   for(i = 0; i < N; i++) {
      for(j = 1; j < 10; j++) {
         m = 0;
         if (D1[i] == j) {
            m++;
         }
         if (m > 1) {
            for(k = 0; k < N; k++) {
               h = 0;
               if (A[k] == j) {
                  L1[h] = B[k];
                  h++;
               }
            }

            for(k = 0; k < N; k++) {
               h = 0;
               if (D1[k] == j) {
                  L2[h] = D2[k];
                  h++;
               }
            }

            for(k = 0; k < N; k++) {
               if (L1[k] != L2[k]) {
                  g2 = 2;
               }
            }
         }
      }
   }

   for(k = 0; k < N - 1; k++) {
      printf("%d%d ", C2[k], C1[k]);
   }
   printf("%d%d\n", C2[N - 1], 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%d ", D2[k], D1[k]);
   }
   printf("%d%d\n", D2[N - 1], D1[N - 1]);

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

   return 0;
}
