Swiss Olympiad in Informatics

Mouse Stofl met a new friend called Victoria a few days ago. Victoria is a famous runner over short and long distances. She has a problem and Stofl wants to help her.
Victoria practices running at a sports facility that offers training paths of many different lengths. All paths are round trips, all beginning and ending at the same point. Now, for each training day in the near future, Victoria has made a very accurate training plan to get even better results at competitions. For each training day, she has written down the distance she would like to run on that day. She measures in the unit '100m' (eg 57 stands for 5.7km) and never wants to run more than 200km on a day. However, since there are so many paths on his training grounds, she is not sure whether it is possible to run exactly the desired distances using the available paths. She asks Stofl to tell her which paths she has to use such that the total distance runned matches exactly the distance needed for her training on each day. Of course, she can run the same path several times if necessary. If several such combinations of paths exist, Stofl's friend prefers using longer paths, because this is more interesting. She also would like to run the longer before the shorter paths.

Given the paths on the training grounds and the distances Mouse Victoria wants to run, compute for every of those distances the combination of paths she should run according to the specifications above.

The first line of the input contains two integers N,M (1 ≤ N,M ≤1000), the number of paths offered on his training grounds and the number of training days of Victoria.
The next N lines each contain one single integer l_i (1 ≤ l_i≤ 2000000), the length of path i.
The last M lines also contain one single integer d_j (1 ≤ d_j ≤ 2000) each, the distance Victoria wants to run on day j.

Print for each training day of Stofl's friend one single line containing the lengths of the paths Victoria has to follow according to the rules above. If it is not possible to run exactly the desired distance on the training ground and this can also not be achieved by combining several paths, output 'Impossible' (without quotes).

You get at least 60% of the points for this task, if you solve correctly all cases where all d_j are smaller than 120 (in the given time limit).

4 5
5
6
9
20
2
20
11
36
95

Impossible
20
6 5
20 6 5 5
20 20 20 20 9 6

Submission form