program.rb

require 'set'
def letter_possibly_match(letter_one, letter_two)
  return true if letter_one == "?" or letter_two == "?"
  return true if letter_one == letter_two
  false
end

# TODO: memoization
def possibly_match(segment_one, segment_two)
  (0...segment_one.size).each do |index|
    return false if not letter_possibly_match(segment_one[index], segment_two[index])
  end
  true
end

# TODO: memoization
def replace_question_marks(segment_one, segment_two)
  result = ""
  (0...segment_one.size).each do |index|
    letter_one = segment_one[index]
    letter_two = segment_two[index]
    if letter_one != "?"
      outcome_letter = letter_one
    elsif letter_two != "?"
      outcome_letter = letter_two
    else
      outcome_letter = "a"
    end
    result << outcome_letter
  end
  result
end

# Returns a list of possible outcomes
def make_match_attempt(table, k1_segments, index = 0, used = Set.new, outcome = [], memo = {})
  return [outcome.sort.join("")] if index == k1_segments.size
  match = used.to_a.join("") + outcome.to_a.join("")
  return memo[match] if memo[match]
  current_k1 = k1_segments[index]
  results = [] #TODO: mutation

  # For each selectable, choose it if possible and create results for the rest
  table[current_k1].each do |k2_segment_selectable|
    next if used.include?(k2_segment_selectable)

    used.add(k2_segment_selectable)
    outcome.push(replace_question_marks(k2_segment_selectable, current_k1))

    results.concat(make_match_attempt(table, k1_segments, index + 1, used, outcome, memo))

    outcome.pop()
    used.delete(k2_segment_selectable)
  end

  memo[match] = results
  return results
end

def calculate(m, k1, k2)
  # Format
  l = k1.length / m
  pattern = /#{"." * l}/
  k1 = k1.scan(pattern)
  k2 = k2.scan(pattern)
  # puts "k1: #{k1} | k2: #{k2}"

  # Build possible chart
  table = k1.inject({}) {|t, segment| t[segment] = []; t}
  # puts "table: #{table}"
  k2.each do |k2_segment|
    table.each do |k1_segment, possibilities|
      possibilities << k2_segment if possibly_match(k1_segment, k2_segment)
    end
  end
  #puts "built table: #{table}"

  # Build Results
  results = make_match_attempt(table, k1)
  # puts "result #{results}"


  return "#{results.size == 0 ? "IMPOSSIBLE" : results[0]}"
end

input = File.open("security.txt")
trials = input.readline.to_i
trials.times do |trial|
  m = input.readline().chomp().split(" ").map(&:to_i)[0]
  key1 = input.readline().chomp()
  key2 = input.readline().chomp()
  puts "Case ##{trial + 1}: #{calculate(m, key1, key2)}"
  # puts "\033[33m---\033[0m"
end