var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
  const N = Number.parseInt(lines[0]);
  const cards = lines[1].split(' ');

  let resultBubble = BubbleSort([...cards], N);
  let isBubbleStable = isStable([...cards], [...resultBubble]);
  console.log(resultBubble.join(' '));
  console.log(isBubbleStable);

  let resultSelect = SelectionSort([...cards], N);
  let isSeletStable = isStable([...cards], [...resultSelect]);
  console.log(resultSelect.join(' '));
  console.log(isSeletStable);
});

function isStable(original, target) {
  for (var i = 0; i < original.length; i++) {
    var numOriginal = parseInt(original[i].slice(1, 2));
    for (var j = 0; j < target.length; j++) {
      var numTarget = parseInt(target[j].slice(1, 2));
      if (numOriginal === numTarget) {
        if (original[i].slice(0, 1) === target[j].slice(0, 1)) {
          target.splice(j, 1);
          break;
        } else {
          return 'Not stable';
        }
      }
    }
  }
  return 'Stable';
}

function BubbleSort(C, N) {
  var cnt = 0;
  while (cnt < N) {
    for(var i = N - 1; i > cnt; i--) {
      var num1 = parseInt(C[i-1].slice(1, 2));
      var num2 = parseInt(C[i].slice(1, 2));
      if (num1 > num2) {
        var tmp = C[i-1];
        C[i-1] = C[i];
        C[i] = tmp;
      }
    }
    cnt++;
  }
  return C;
}

function SelectionSort(C, N) {
  for (var i = 0; i < N - 1; i++) {
    var minj = parseInt(C[i].slice(1, 3));
    var minArrayNumber = i;
    for (var j = i + 1; j < N; j++) {
      var val = parseInt(C[j].slice(1, 3));
      if (minj > val) {
        minj = val;
        minArrayNumber = j;
      }
    }
    var tmp = C[i];
    C[i] = C[minArrayNumber];
    C[minArrayNumber] = tmp;
  }
  return C;
}

