let inputString = '';

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});
process.stdin.on('end', function() {
    inputString = inputString.replace(/\s*$/, '')
        .split('\n')
        .map(str => str.replace(/\s*$/, ''));

    stableSort(inputString[1].split(' '));
});

const stableSort = (arr) => {
  const arrForBubbleSort = [...arr];
  bubbleSort(arrForBubbleSort);

  const arrForSelectionSort = [...arr];
  selectionSort(arrForSelectionSort);

  console.log(arrForBubbleSort.join(' '));
  console.log('Stable'); // bubble sort is always stable
  console.log(arrForSelectionSort.join(' '));
  console.log(arrForSelectionSort.every((v, i) => v === arrForBubbleSort[i]) ? 'Stable' : 'Not stable');
};

const bubbleSort = (arr) => {
  let swapped = true;
  for (let i=0; swapped; i++) {
    swapped = false;
    for (let j=arr.length-1; j>i; j--) {
      const left = arr[j - 1];
      const right = arr[j];
      if (Number(left[1]) > Number(right[1])) {
        arr[j] = left;
        arr[j - 1] = right;
        swapped = true;
      }
    }
  }
};

const selectionSort = (arr) => {
  for (let i=0; i<arr.length; i++) {
    let minj = i;
    for (let j=i; j<arr.length; j++) {
      if (Number(arr[minj][1]) > Number(arr[j][1])) {
        minj = j;
      }
    }
    const a = arr[i];
    const b = arr[minj];
    arr[i] = b;
    arr[minj] = a;
  }
};

