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

num = gets.to_i

#aryB: array for Bubble Sort
aryB = gets.split
#aryS: array for Selection Sort
aryS = Marshal.load(Marshal.dump(aryB))
#aryStable: Sorted stability
aryStable = Marshal.load(Marshal.dump(aryB))

#---------------------------------------------------------------------#
#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

#---------------------------------------------------------------------#
#Stable Sort

aryStable = Marshal.load(Marshal.dump(aryB))

index_last = num - 2

while index_last >= 0

  for i in 0 .. index_last

    if aryStable[i][1] == aryStable[i + 1][1] && aryStable[i][0] > aryStable[i + 1][0]
      aryStable[i], aryStable[i + 1] = aryStable[i + 1], aryStable[i]
    end
  end

  index_last -= 1
end

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

#Bubble Sort
puts aryB.join(" ")
puts aryB == aryStable ? "Stable" : "Not stable"

#Bubble Sort
puts aryS.join(" ")
puts aryS == aryStable ? "Stable" : "Not stable"

