#---------------------------------------------------------------------#
#Initialize

num = gets.to_i
ary_original = gets.split

#aryB: array for Bubble Sort
aryB = Marshal.load(Marshal.dump(ary_original))

#aryS: array for Selection Sort
aryS = Marshal.load(Marshal.dump(ary_original))

def stable? (ary, org)

  (ary.size - 1).times do |i|

    if ary[i][1] == ary[i+1][1]
      if org.index(ary[i]) > org.index(ary[i+1])
        return "Not stable"
      end
    end

  end

  return "Stable"

end

#---------------------------------------------------------------------#
#Bubble Sort

index_last = num - 2

while index_last >= 0

  for i in 0 .. index_last

    if aryB[i][1] > aryB[i + 1][1]
      aryB[i], aryB[i + 1] = aryB[i + 1], aryB[i]
    end

  end

  index_last -= 1

end

#---------------------------------------------------------------------#
#Selection Sort

for i in 0 .. num-2

  min = aryS[i][1]
  min_index = i

  for j in i .. num-1

    if min > aryS[j][1]
      min = aryS[j][1]
      min_index = j
    end

  end

  if aryS[i][1] != aryS[min_index][1]
    aryS[i], aryS[min_index] = aryS[min_index], aryS[i]
  end

end

#---------------------------------------------------------------------#
#Output

#Bubble Sort
puts aryB.join(" ")
puts stable?(aryB, ary_original)

#Bubble Sort
puts aryS.join(" ")
puts stable?(aryS, ary_original)

