const largerThan = (a, b) => {
  let an = a.slice(1);
  let bn = b.slice(1);
  return an > bn;
};

const bubbleSort = (n, a) => {
  let isChanged = true;
  let index = 0;
  while (isChanged) {
    isChanged = false;
    for (let j = n - 1; j > index; j--) {
      if (largerThan(a[j - 1], a[j])) {
        let tmp = a[j - 1];
        a[j - 1] = a[j];
        a[j] = tmp;
        isChanged = true;
      }
    }
    index += 1;
  }
  console.log(a.join(" "));
  console.log("Stable");
};

const selectionSort = (n, a) => {
  let stable = true;
  for (let i = 0; i < n; i++) {
    minIndex = i;
    for (let j = i; j < n; j++) {
      if (largerThan(a[minIndex], a[j])) {
        minIndex = j;
      }
    }
    if (minIndex != i) {
      let tmp = a[minIndex];
      a[minIndex] = a[i];
      a[i] = tmp;
      stable = false;
    }
  }
  console.log(a.join(" "));
  console.log(stable ? "Stable" : "Not stable");
};

// bubbleSort("5", "H4 C9 S4 D2 C3".split(" "));
// selectionSort("5", "H4 C9 S4 D2 C3".split(" "));

process.stdin.resume();
process.stdin.setEncoding("utf8");
let input_string = "";

process.stdin.on("data", chunk => {
  input_string += chunk;
});

process.stdin.on("end", () => {
  const lines = input_string.split("\n").filter(v => {
    return v !== "";
  });
  bubbleSort(lines[0], lines[1].split(" ").map(i => parseInt(i, 10)));
  selectionSort(lines[0], lines[1].split(" ").map(i => parseInt(i, 10)));
});

