# 入力される配列の長さ
 array_length = gets.to_i

# #入力される配列
 array_value = gets.chomp.split(" ")

array_value_for_bubble = array_value.clone
array_value_for_selection = array_value.clone


# puts array_value_for_bubble.object_id
# puts array_value_for_selection.object_id
#stable or not judgement function
def stableOrNotJudgement(before_array, after_array, array_length)
    #0でstable 1でnot stable
    result_flag = 0
    
    0.upto(array_length - 2) do |i|
        array_val_i = after_array[i]
        array_val_i_plus_1 = after_array[i + 1]
        
        if array_val_i.split("")[1].to_i == array_val_i_plus_1.split("")[1].to_i
            result_flag = before_array.index(array_val_i) > before_array.index(array_val_i_plus_1) ? 1 : 0
            
        end
        
        break if result_flag == 1
    end
    
    result = result_flag == 1 ? "Not stable" : "Stable"
    result_flag = 0
    return result
    
    
end

# bubble sort function
def BubbleSort(bubble_input_array, bubble_input_array_length)
    for i in 0..(bubble_input_array_length - 1)
        (bubble_input_array_length - 1).downto(i + 1) do |j|
            # インデックスが小さい方の値が小さい場合には値を交換
            if bubble_input_array[j].split("")[1].to_i < bubble_input_array[j - 1].split("")[1].to_i
                bubble_input_array[j], bubble_input_array[j - 1] = bubble_input_array[j - 1], bubble_input_array[j]
                
            end
        end
    end
end

BubbleSort(array_value_for_bubble, array_length)
puts array_value_for_bubble.join(" ")
puts stableOrNotJudgement(array_value, array_value_for_bubble, array_length)

#selection sort function
def SelectionSort(selection_input_array, array_length)
    for i in 0..(array_length - 1)
    minj = i
        for j in i..(array_length - 1)
            if selection_input_array[j].split("")[1].to_i < selection_input_array[minj].split("")[1].to_i
                minj = j
            end
            
        end
        selection_input_array[i],selection_input_array[minj] = selection_input_array[minj],selection_input_array[i] 
    end
    
end



SelectionSort(array_value_for_selection, array_length)
puts array_value_for_selection.join(" ")
puts stableOrNotJudgement(array_value, array_value_for_selection, array_length)
