def selectionsort(a)
    (0...a.size).each{|i|
        minj = i
        (i...a.size).each{|j|
            minj = j if a[j][1]<a[minj][1]
        }
        a[i], a[minj] = a[minj], a[i] if i!=minj
    }
end

gets
a = gets.split

bs = a.sort_by{|a| a[1]}

selectionsort a
puts bs.join(' '), "Stable", a.join(' '), (a==bs ? "Stable" : "Not stable")
