var input = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
var n = +input.shift();
var cards = input.shift().split(' ');

function bubbleSort(input) {
  var cards = [].concat(input);

  for (var i = 0; i < cards.length; i++) {
    for (var j = cards.length - 1; j > i; j--) {
      if ((+cards[j][1]) < (+cards[j - 1][1])) {
        var tmp = cards[j];
        cards[j] = cards[j - 1];
        cards[j - 1] = tmp;
      }
    }
  }

  return cards;
}

function selectionSort(input) {
  var cards = [].concat(input);

  for (var i = 0; i < cards.length; i++) {
    var minIndex = i;
    for (var j = i; j < cards.length; j++) {
      if ((+cards[j][1]) < (+cards[minIndex][1])) minIndex = j;
    }

    if (minIndex !== i) {
      var tmp = cards[i];
      cards[i] = cards[minIndex];
      cards[minIndex] = tmp;
    }
  }

  return cards;
}

function isStable(bubble, selection) {
  if (bubble === selection) {
    return 'Stable';
  } else {
    return 'Not stable';
  }
}

function stableSort(cards) {
  var bubble = bubbleSort(cards);
  var selection = selectionSort(cards);

  console.log(bubble.join(' '));
  console.log('Stable');
  console.log(selection.join(' '));
  console.log(isStable(bubble, selection));
}

stableSort(cards);