Choosing the Final Die's Face Values

Phil Kropotnik is a game designer, and one problem he often runs into is deciding which set of dice to use in a game. Many modern games call for non-traditional dice — dice with more or fewer sides than the usual 6-sided cube.

Phil usually fixes the face values of all but the last die, then works out what values to put on the last die so that certain sums can be rolled in certain numbers of ways. (Instead of dealing with probabilities, he works directly with the total number of different ways a given sum can be obtained by rolling all the dice.) He currently does this by hand; your task is to automate it.

When several dice are rolled together, the number of ways to obtain a sum is the number of distinct combinations of one face from each die. If the same value appears on several faces, those faces are treated as distinct.

For example, suppose Phil already has a 4-sided die with face values 1, 10, 15, and 20, and he wants to label a 5-sided die so that, using both dice, there are (a) 3 ways to obtain a sum of 2, (b) 1 way to obtain 3, (c) 3 ways to obtain 11, (d) 4 ways to obtain 16, and (e) 1 way to obtain 26. He should label the faces of the 5-sided die 1, 1, 1, 2, and 6. (For instance, the sum 16 can be made as 10 + 6 or as 15 + 1; since there are three '1' faces on the second die, this gives 4 different ways in total.)

Given the already-specified dice, the number of faces on the last die, and the desired (sum, count) requirements, determine the face values of the last die.

The input consists of several input sets. Each input set begins with a single line containing an integer $n$, the number of dice already specified. Each of the next $n$ lines describes one of these dice: the line starts with an integer $f$ (the number of faces on the die), followed by $f$ integers giving the value of each face.

The last line of each set has the form

r m v1 c1 v2 c2 v3 c3 ··· vm cm

where $r$ is the number of faces required on the unspecified die, $m$ is the number of sums of interest, $v_1, \dots, v_m$ are those sums, and $c_1, \dots, c_m$ are the required numbers of different ways to obtain each corresponding sum.

The input satisfies: $1 \le n \le 20$, $3 \le f \le 20$, $1 \le m \le 10$, and $4 \le r \le 6$. The face values of all dice, both the specified ones and the unknown die, are integers from $1$ to $50$. The values $v_i$ and $c_i$ are all non-negative and strictly less than the maximum value of a 32-bit signed integer.

The last input set is followed by a line containing a single $0$, which should not be processed.

For each input set, print a single line containing either the phrase Final die face values are followed by the $r$ face values in non-descending order, or Impossible if no die meets the specification.

If several dice satisfy the requirements, choose the one whose smallest face value is smallest; if there is still a tie, choose the one whose second-smallest face value is smallest, and so on.