#Stable Sort


#Swap???????????????????????????
def Swap(a, b)
    return b, a
end

#BubbleSort????????????
def BubbleSort(chars, numbers, length)
    for i in 0..length-1
        for j in i+1..length-1
            k = (i + 1) + (length - 1) - j
            if numbers[k] < numbers[k-1] then
                chars[k], chars[k-1] = Swap(chars[k], chars[k-1])
                numbers[k], numbers[k-1] = Swap(numbers[k], numbers[k-1])
            end
        end
    end
    #??????????????????????????????main?????????
    return chars, numbers
end

#SelectionSort????????????
def SelectionSort(chars, numbers, length)
    for i in 0..length-1
        mini = i
        for j in i..length-1
            if numbers[j] < numbers[mini] then
                mini = j
            end
        end
        chars[i], chars[mini] = Swap(chars[i], chars[mini])
        numbers[i], numbers[mini] = Swap(numbers[i], numbers[mini])
    end
    return chars, numbers
end

#????????????????????????????????¨?????????????????????
def PrintBubbleSort(chars, numbers, length)
    i = -1
    for i in 0..length-2
        print chars[i], numbers[i], " "
    end
    print chars[i+1], numbers[i+1], "\n"
    print "Stable\n"
end

#?????????????????????????????¨?????????????????????
def PrintSelectionSort(chars, numbers, length)
    i = -1
    flag = 0
    for i in 0..length-2
        print chars[i], numbers[i], " "
    end
    print chars[i+1], numbers[i+1], "\n"

    # ??£????????£???????????°??????????????????????????????????????????
    #??£????????£???????????°?????????????????£?????????Stable??§?????????
    for i in 1..length-1
        if numbers[i] == numbers[i-1] then
            flag = 1
        end
    end

    #????????°????????£????????£?????????????????°???Stable?????¨????????????
    if flag == 0 then
        print "Stable\n"
    else
        print "Not stable\n"
    end
end

#?????????????????°
chars = []
numbers = []
chars2 = []
numbers2 = []

length = readline.to_i

#??\?????????????????????????????????????´??????????
pair = gets.chomp.split(" ")

#??\????????????????????????????????¨??°???????????¢??????????????????????????????????´??????????
for i in 0..length-1
    #?????????????????±???(?????????)??¨??°???(?????????)????????¢??????
    chars[i], numChar = pair[i].split("")
    chars2[i], numChar2 = pair[i].split("")

    #??°???(?????????)?????°????????????
    numbers[i] = numChar.to_i
    numbers2[i] = numChar2.to_i
end

bchars, bnumbers = BubbleSort(chars, numbers, length)
PrintBubbleSort(bchars, bnumbers, length)

schars, snumbers = SelectionSort(chars2, numbers2, length)
PrintSelectionSort(schars, snumbers, length)