/**
 * ??????????????????
?????????????????????????????´?????????????????????????????§?????????????????????(S, H, C,
D)??¨???????????°???(1, 2, ..., 9)???????§??????????????¨? 36
????????????????????¨????????????????????°??????????????? 8 ???"H8"??????????????? 1 ???"D1"??¨??¨????????????

????????????????????????????????????????????¢?????´??????????????¨???????????????????????? N
????????????????????????????????°??????????????????????????´?????????????????°??????????????????????????????????????¢?????´??????????????????????????\????????????????????????????????????????????¨??????????????°??????????´????
0 ??????????????§?¨???°?????????????????????

1 BubbleSort(C, N)
2   for i = 0 to N-1
3     for j = N-1 downto i+1
4       if C[j].value < C[j-1].value
5         C[j] ??¨ C[j-1] ?????????
6
7 SelectionSort(C, N)
8   for i = 0 to N-1
9     minj = i
10    for j = i to N-1
11      if C[j].value < C[minj].value
12        minj = j
13    C[i] ??¨ C[minj] ?????????
??????????????¢?????´?????????????????????????????????????????\??????????????????????????????????????£??????????????±????????????????????????????????§??????????????°?????????????????????????????°????????´?????????????????\??????????????????????????§????????????????????¨?????????????????????????????¨?????¶?????¨?????????????????????????????????????????????????????????????????¢?????´????????????????????????????????¢?????´???????????¨?¨????????????????

??\???
1 ??????????????????????????° N ???????????????????????? 2 ????????? N
??????????????????????????????????????????????????????????????¨??°???????????¢?????¨??????????????§???????????£???????????????????????????????????§???????????????????????????

??????
1
??????????????????????????????????????£?????´??????????????????????????????????????????????????????????????£???????????????????????????????????§????????£??????????????????
2 ?????????????????????????????????????????????Stable ?????????Not stable?????????????????????????????????
3
???????????????????????????????????£?????´??????????????????????????????????????????????????????????????£???????????????????????????????????§????????£??????????????????
4 ?????????????????????????????????????????????Stable ?????????Not stable?????????????????????????????????

??¶?´?
1 ??? N ??? 36
??\?????? 1
5
H4 C9 S4 D2 C3
????????? 1
D2 C3 H4 S4 C9
Stable
D2 C3 S4 H4 C9
Not stable
??\?????? 2
2
S1 H1
????????? 2
S1 H1
Stable
S1 H1
Stable
 */

#include <iostream>
#include <iterator>
#include <sstream>
#include <vector>

void bubbleSort(std::vector<std::string> &Cards) {
  unsigned short N = Cards.size();
  for (size_t i = 0; i < N; i++) {
    for (size_t j = N - 1; j >= i + 1; j--) {
      if (Cards[j][1] < Cards[j - 1][1]) {
        std::swap(Cards[j], Cards[j - 1]);
      }
    }
  }
}

void selectionSort(std::vector<std::string> &Numbers) {
  const size_t n = Numbers.size();
  unsigned short minj;

  for (size_t i = 0; i < n; i++) {
    minj = i;
    for (size_t j = i; j < n; j++) {
      if (Numbers[j][1] < Numbers[minj][1]) {
        minj = j;
      }
    }
    std::swap(Numbers[i], Numbers[minj]);
  }
}

void printVector(const std::vector<std::string> &v) {
  std::ostringstream oss;
  std::copy(v.begin(), v.end() - 1,
            std::ostream_iterator<std::string>(oss, " "));
  oss << v.back();
  std::cout << oss.str() << std::endl;
}

int main(int argc, char const *argv[]) {
  unsigned int N;
  std::string Param;

  while (true) {

    getline(std::cin, Param);
    std::istringstream iss(Param);
    iss >> N;
    iss.clear();

    if (N < 1 || N > 36) {
      std::cout << "Error: 1 <= N <= 36" << std::endl;
    } else {
      break;
    }
  }
  std::vector<std::string> Cards(N);
  getline(std::cin, Param);
  std::istringstream iss(Param);
  for (size_t i = 0; i < N; i++) {
    iss >> Cards[i];
  }
  std::vector<std::string> Cards1(Cards);
  std::vector<std::string> Cards2(Cards);
  bubbleSort(Cards1);
  printVector(Cards1);
  std::cout << "Stable" << std::endl; // Bubble sort is stable.
  selectionSort(Cards2);
  printVector(Cards2);
  if (Cards1 == Cards2) {
    std::cout << "Stable" << std::endl;
  } else {
    std::cout << "Not stable" << std::endl;
  }

  return 0;
}

Measured memory_bytes: 3168