process.stdin.resume();
process.stdin.setEncoding("utf8");

const reader = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];

reader.on("line", (line) => {
  lines.push(line);
});

const compare = (lhs, rhs) => {
  const [l, r] = [lhs[1], rhs[1]];
  return l < r ? -1 : l > r ? 1 : 0;
};

const bubbleSort = (a) => {
  a = a.slice();
  const len = a.length;
  for (let i = 0; i < len; i++) {
    for (let j = len - 1; j > i; j--) {
      if (compare(a[j], a[j - 1]) < 0) {
        const t = a[j];
        a[j] = a[j - 1];
        a[j - 1] = t;
      }
    }
  }
  return a;
};

const selectionSort = (a) => {
  a = a.slice();
  const len = a.length;
  for (let i = 0; i < len; i++) {
    let minj = i;
    for (let j = i; j < len; j++) {
      if (compare(a[j], a[minj]) < 0) {
        minj = j;
      }
    }
    const t = a[i];
    a[i] = a[minj];
    a[minj] = t;
  }
  return a;
};

const isStable = (a1, a2) => {
  let isEq = true;
  Array(9)
    .fill()
    .map((e, i) => "" + (i + 1))
    .map((e) => {
      if (!isEq) return;

      const aa1 = a1.reduce((p, card) => {
        if (card[1] === e) {
          p.push(card[0]);
        }
        return p;
      }, []);
      const aa2 = a2.reduce((p, card) => {
        if (card[1] === e) {
          p.push(card[0]);
        }
        return p;
      }, []);
      for (let i = 0; i < aa1.length; i++) {
        if (aa1[i] !== aa2[i]) {
          isEq = false;
          break;
        }
      }
    });

  return isEq;
};

reader.on("close", () => {
  let ns = lines[1].split(" ");
  const a1 = bubbleSort(ns);
  const a2 = selectionSort(ns);
  console.log(a1.join(" "));
  console.log(isStable(a1, ns) ? "Stable" : "Not stable");
  console.log(a2.join(" "));
  console.log(isStable(a2, ns) ? "Stable" : "Not stable");
});

