var getValue = function(str) {
  return parseInt(str.slice(1), 10);
};

var bubbleSort = function(arr, n) {
  var c = arr.slice();
  for (var i = 0; i <= n - 1; i += 1) {
    for (var j = n - 1; j >= i + 1; j -= 1) {
      if (getValue(c[j]) < getValue(c[j - 1])) {
        var temp = c[j];
        c[j] = c[j - 1];
        c[j - 1] = temp;
      }
    }
  }
  return c;
};

var selectionSort = function(arr, n) {
  var c = arr.slice();
  for (var i = 0; i <= n - 1; i += 1) {
    var minj = i;
    for (var j = i; j <= n - 1; j += 1) {
      if (getValue(c[j]) < getValue(c[minj])) {
        minj = j;
      }
    }
    var temp = c[i];
    c[i] = c[minj];
    c[minj] = temp;
  }
  return c;
};

var input = require('fs').readFileSync('/dev/stdin', 'utf8');
input.split('\n').forEach(function(line, i) {
  if (line !== '' && i % 2 === 1) {
    var nums = line.split(' ');
    var bubbleSorted = bubbleSort(nums, nums.length);
    console.log(bubbleSorted.join(' '));
    console.log('Stable');
    var selectionSorted = selectionSort(nums, nums.length);
    console.log(selectionSorted.join(' '));
    if (selectionSorted.join(' ') === bubbleSorted.join(' ')) {
      console.log('Stable');
    } else {
      console.log('Not stable');
    }
  }
});