def bubble_sort(a)
????arr = a.dup
????n = arr.length
????for i in 0..n - 1
????????j = n - 1
????????while j > i
????????????if arr[j-1][1] > arr[j][1]
????????????????arr[j-1],arr[j] = arr[j],arr[j-1]
????????????end
????????????j -= 1
????????end
????end
????arr
end
??
def selection_sort(arr)
????a = arr.dup
????for i in 0..(a.length - 1)
????????min = i
????????for j in i ..(a.length - 1)
????????????if a[j][1] < a[min][1]
????????????????min = j
????????????end
????????end
????????a[i], a[min] = a[min], a[i]
????end
????a
end
??
gets
x = gets.split.map { |v| [v[0], v[1].to_i] }
b = bubble_sort(x)
s = selection_sort(x)
??
puts b.map(&:join).join(' ')
puts 'Stable'
puts s.map(&:join).join(' ')
puts b == s ? 'Stable' : 'Not stable'