n = gets
arr = gets.chomp.split
arro = arr.clone
arr0 = arr.clone
arr1 = arr.clone

def bubble_sort(arr)
  count = 0
  arr.length.times do |i|
    j = arr.length - 1
    while j >= i+1
      if(arr[j-1][1] > arr[j][1])
        tmp = arr[j-1]
        arr[j-1] = arr[j]
        arr[j] = tmp
      end
      j -= 1
    end
    count += 1
  end
  puts arr.join(' ')
  puts 'Stable'
  return arr
end

def select_sort(arr)
  arr.length.times do |i|
    mini = i
    j = i
    while j < arr.length
      if(arr[j][1] < arr[mini][1])
        mini = j
      end
      j += 1
    end
    if(i != mini)
      temp = arr[i]
      arr[i] = arr[mini]
      arr[mini] = temp
    end
  end
  puts arr.join(' ')
  puts is_stable(@std, arr)
end

def is_stable(std, arr)
  arr.length.times do |i|
    return "Not stable" if(std[i] != arr[i])
  end
  return "Stable"
end

@std = bubble_sort(arr0)
select_sort(arr1)
