Problem G
Restaurant Orders

A friend of yours who is working as a waiter has a problem. A group of xkcd-fans have started to come to the restaurant and order food as in the comic strip below. Each order takes him a lot of time to figure out, but maybe you can help him.

\includegraphics[width=0.7\textwidth ]{np_complete.png}
Figure 1: Comic strip xkcd.com/287.


You are to write a program that finds out what was ordered given the total cost of the order and the cost of each item on the menu.


The input starts with a line containing one integer $n$ ($1\leq n\leq 100$), the number of items on the menu. The next line contains $n$ space-separated positive integers $c_1, c_2, \dots , c_ n$, denoting the cost of each item on the menu in Swedish kronor. No item costs more than $1\, 000$ SEK.

This is followed by a line containing $m$ ($1\leq m\leq 1\, 000$), the number of orders placed, and a line with $m$ orders. Each order is given as an integer $s$ ($1\leq s\leq 30\, 000$), the total cost of all ordered items in SEK.


For each order in the input output one line as follows. If there is one unique order giving the specified total cost, output a space-separated list of the numbers of the items on that order in ascending order. If the order contains more than one of the same item, print the corresponding number the appropriate number of times. The first item on the menu has number 1, the second 2, and so on.

If there doesn’t exist an order that gives the specified sum, output Impossible. If there are more than one order that gives the specified sum, output Ambiguous.

Sample Input 1 Sample Output 1
4 5 8
11 13 14
1 2 2
Sample Input 2 Sample Output 2
215 275 335 355 420 580

Please log in to submit a solution to this problem

Log in