function main(input) {
  input = input.split("\n");
  var N = parseInt(input[0]);
  var values = input[1].split(" ");//.map(function(v) { return parseInt(v); });


  var getType = function(a, index) {
    return a[index][0];
  };
  var getNum = function(a, index) {
    return parseInt(a[index][1]);
  };


  var values1 = values.concat();
  bubbleSort(values1, N, function(a, index) {
    return parseInt(a[index][1]);
  });
  console.log(values1.join(" "));
  if (isStable(values, values1, N, getType, getNum)) {
    console.log("Stable");
  } else {
    console.log("Not stable");
  }

  var values2 = values.concat();
  selectionSort(values2, N, function(a, index) {
    return parseInt(a[index][1]);
  });
  console.log(values2.join(" "));
  if (isStable(values, values2, N, getType, getNum)) {
    console.log("Stable");
  } else {
    console.log("Not stable");
  }
}

function isStable(org, a, N, type, num) {
  var i = 0;
  var table = {};
  for (i = 0; i < N; i++) {
    var n = num(org, i);
    if (table[n] == null) table[n] = [];
    table[n].push(type(org, i));
  }

  for (var key in table) {
    var values = table[key];
    var count = 0;
    for (i = 0; i < N; i++) {
      if (num(a, i) == key) {
        if (values[count] == type(a, i)) {
          count++;
        } else {
          return false;
        }
      }
    }
  }
  return true;
}

function bubbleSort(a, N, get) {
  var flag = true;
  while (flag) {
    flag = false;
    for (var j = N-1; j >= 1; j--) {
      if (get(a, j) < get(a, j-1)) {
        var v = a[j];
        a[j] = a[j-1];
        a[j-1] = v;
        flag = true;
      }
    }
  }
}

function selectionSort(a, N, get) {
  for (var i = 0; i < N; i++) {
    var minj = i;
    for (var j = i; j < N; j++) {
      if (get(a, j) < get(a, minj)) {
        minj = j;
      }
    }

    if (minj != i) {
      var tmp = a[i];
      a[i] = a[minj];
      a[minj] = tmp;
    }
  }
}


main(require("fs").readFileSync("/dev/stdin", "utf8"));