ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

NEERC, Eastern subregion, Yekaterinburg, October 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. Japanese Puzzle

Time limit: 1.0 second
Memory limit: 64 MB
Solving Japanese puzzles (or Paint by numbers, as they are often called) is a very popular pastime among New Russians. In this kind of puzzle, cells in a grid have to be painted black or left blank according to numbers given at the sides of the grid. If this is done correctly, a hidden picture is revealed. The numbers are the lengths of continuous segments of painted cells in any given row or column. For example, a clue of "4 8 3" would mean there are segments of four, eight, and three filled cells, in that order, with at least one blank cell between successive groups. Of course, programmers are not as clever as New Russians, so we don't ask you to solve the whole puzzle. Your task will be to write a program that yields as much information about each cell of one row of a puzzle as possible, given some data about this row.

Input

The first line contains the length of the row L (1 ≤ L ≤ 400) and the number of groups of consecutive cells that must be painted K (0 ≤ K ≤ L). The second line contains K integers, which are the lengths of these groups. The third line contains L symbols describing the current information about the cells of the row (this information could be obtained by means of analyzing the data for columns and other rows):
'.' denotes a cell that is definitely blank,
'X' denotes a cell that must definitely be painted,
'?' means that there is no information about this cell.

Output

Output a line containing L symbols describing the most complete information about the cells of the row in the same format as in the input, or the word Impossible if the input information is inconsistent and there is no row satisfying the input data.

Samples

inputoutput
10 2
4 2
?????.?X??
?XXX?.?X?.
9 0

??????.X?
Impossible
Problem Author: Stanislav Vasilyev
Problem Source: Quarter-Final of XXXI ACM ICPC - Yekaterinburg - 2006
To submit the solution for this problem go to the Problem set: 1508. Japanese Puzzle