Nonogram Row Logic

In a nonogram, numbers beside each row of a hidden picture give the lengths of the runs of filled squares in that row, in order from left to right, with at least one empty square between two runs. For example, the clue [3, 1] in a row of 6 squares fits ###.#., ###..# and .###.#.

Solvers work one row at a time and fill in only what is certain. Write solve_line(clues, line), where line is the row as far as it is known: '#' is a filled square, '.' an empty square and '?' a square not decided yet. Think of every way to place the runs that agrees with clues and with the squares already known. Return the row with each '?' replaced by '#' if that square is filled in every one of those ways, by '.' if it is empty in every one of them, and left as '?' otherwise. Known squares stay as they are.

Examples

solve_line([3, 1], '??????')   # returns '?##???'
solve_line([4], '?????')       # returns '?###?'
solve_line([2], '?#???')       # returns '?#?..'
solve_line([1, 1], '?.?#?')    # returns '#..#.'

In the first example the run of 3 covers squares 1 and 2 however it is placed, and nothing else is certain. In the last one the known '#' must be the second run, so its neighbours are empty, and the first run has to be the first square.

Constraints

• line has 1 to 1,000 squares; clues has 0 to 200 numbers, each at least 1.
• At least one placement of the runs agrees with line.
• With an empty clues, the whole row is empty.