def bubble_sort(data, test_proc = proc { |a, b| (a <=> b) > 0 } )
  n = data.size
  loop {
    orderd = true
    0.upto(n - 2) { |i|
      if test_proc.call(data[i], data[i + 1])
        tmp = data[i]
        data[i] = data[i + 1]
        data[i + 1] = tmp
        orderd = false
      end
    }
    break if orderd
  }
  data
end

def selection_sort(data, test_proc = proc { |a, b| (a <=> b) > 0 } )
  n = data.size
  0.upto(n - 2) { |i|
    swap_idx = i
    i.upto(n - 1) { |j|
      swap_idx = j if test_proc.call(data[swap_idx], data[j])
    }
    tmp = data[i]
    data[i] = data[swap_idx]
    data[swap_idx] = tmp
  }
  data
end

def stable_sort?(original, sorted)
  0.upto(sorted.size - 2) { |i|
    if sorted[i][1] == sorted[i + 1][1]
      is_not_stable = false
      original.each { |a|
        if a == sorted[i]
          break
        elsif a == sorted[i + 1]
          is_not_stable = true
          break
        end
      }
      if is_not_stable
        return false
      end
    end
  }
  true
end

data = $stdin.read.lines[1].split(' ').each { |n| n.instance_eval { def <=>(other); self[1].to_i <=> other[1].to_i; end } }
[bubble_sort(data.clone), selection_sort(data.clone)].each { |sorted|
  puts sorted.join(' ')
  puts stable_sort?(data, sorted) ? 'Stable' : 'Not stable'
}