
let int = parseInt;

function main(input){
    let lines = input.split("\n");
    let length = int(lines[0]);
    let cards = lines[1].split(" ");
    let bubbleSorted = bubble(length,cards);
    echoArray(bubbleSorted);
    judgeStable(cards,bubbleSorted);
    let selectSorted = select(length,cards);
    echoArray(selectSorted);
    judgeStable(cards,selectSorted);

}

function judgeStable(original,sorted){
    let stableSorted = bubble(original.length,original);
    let isStable = true;
    for(let i=0;i<stableSorted.length;i++){
        if(stableSorted[i]!==sorted[i]){
            isStable = false;
            break;
        }
    }
    if(isStable){
        console.log("Stable");
    }else{
        console.log("Not stable");
    }
    
    
}

function devide(array){
    let strArray = array.map(item=>item.slice(0,1));
    let numArray = array.map(item=>int(item.slice(1)));
    return {
        "strArray":strArray,
        "numArray":numArray
    }
}
function combine(strArr,numArr){
    let arr=[];
    for(let i=0;i<strArr.length;i++){
        arr[i] = strArr[i]+String(numArr[i])+" ";
    }
    return arr;
    
}
function echoArray(array){
    let put ="";
    for(let i=0;i<array.length;i++){
        put+=array[i];
    }
    console.log(put.trim());
}

function bubble(N,array){
    const devided = devide(array);
    let strArray = devided.strArray;
    let numArray = devided.numArray;
    let swapped;
    let sortedIndex=0;
    
    do{
        swapped = false;
        for(let i=N;i>sortedIndex;i--){
         if(numArray[i]<numArray[i-1]){
             let temp = numArray[i];
             numArray[i] = numArray[i-1];
             numArray[i-1] = temp;
             let strTemp = strArray[i];
             strArray[i] = strArray[i-1];
             strArray[i-1] = strTemp;
             swapped = true;
             
         }
        }
        sortedIndex++;
    }while(swapped);
    
    let result = combine(strArray,numArray);
    return result;
}

function select(N,array){
    const devided = devide(array);
    let strArr = devided.strArray;
    let numArr = devided.numArray;
    
    let minIndex=0;
    
    for(let i=0;i<N;i++){
        minIndex = i;
        for(let j=i;j<N;j++){
            if(numArr[j]<numArr[minIndex]){
                minIndex = j;
            }
        }
        let temp = numArr[i];
        numArr[i] = numArr[minIndex];
        numArr[minIndex] = temp;
        let strTemp = strArr[i];
        strArr[i] = strArr[minIndex];
        strArr[minIndex] = strTemp;
    }
    let result = combine(strArr,numArr);
    return result;
    
    
    
}

main(require("fs").readFileSync("/dev/stdin","utf-8"));
