Card = Struct.new(:suit, :rank) {
  def value
    rank
  end

  def to_s
    "#{suit}#{rank}"
  end
}

def bubble_sort(arr)
  has_unordered = true
  stable = true

  while has_unordered
    has_unordered = false

    for i in (1...arr.length).to_a.reverse
      if (x=arr[i]).value < arr[i-1].value
        arr[i] = arr[i-1]
        arr[i-1] = x
        has_unordered = true
        stable = false if arr[i].value == arr[i-1].value
      end
    end
  end

  puts arr.join(" ")
  puts stable ? "Stable" : "Not stable"
end

def selection_sort(a) # N個の要素を含む0-オリジンの配列A
  stable = true
  for i in 0...(a.length)
    found_same_value = false
    minj = i
    for j in i...(a.length)
      case a[j].value <=> a[minj].value
      when -1
        minj = j
        stable = false if found_same_value
      when 0
        found_same_value = true if j != i
      end
    end
    old_ai = a[i]
    a[i] = a[minj]
    a[minj] = old_ai
  end

  puts a.join(" ")
  puts stable ? "Stable" : "Not stable"
end

gets

arr = gets.split.map{|card| Card.new(card[0], card[1].to_i)}

bubble_sort(arr.clone)
selection_sort(arr.clone)

