*Not an official ACM page*

[ Problem D
| 1998 ACM Finals problem set
| My ACM problem archive
| my home page]

The 1998 22nd Annual
**acm**
International Collegiate

Programming Contest World Finals

sponsored by **IBM**

##
Problem C

Lead or Gold

How to make gold from lead has baffled alchemists for centuries. At
the last Alchemists Club Meeting (ACM), a sensational breakthrough was
announced. By mixing the three chemicals Algolene, Basicine and
Cobolase in the correct ratio, one can create a mixture that
transforms lead into gold. Since Algolene, Basicine and Cobolase (or
A, B, C for short) are generally not sold individually, but rather
mixed into solutions, this may not be easy as it seems.
Consider the following example. Two mixtures of Algolene, Basicine and
Cobolase are available, in ratios of 1:2:3 and 3:7:1, respectively. By
mixing these solutions in a ratio of 1:2 we obtain a solution of A, B,
C with ratio 7:16:5. But there is no way to combine these mixtures
into a new one with ratio 3:4:5. If we additionally had a solution of
ratio 2:1:2, then a 3:4:5 mixture would be possible by combining eight
parts of 1:2:3, one part of 3:7:1 and five parts of 2:1:2.

Determining which mixing ratios we can obtain from a given set of
soluti ons is no trivial task. But, as the ACM has shown, it is
possibly a very profitable one. You must write a program to find
mixing ratios.

### Input

The input file contains several test cases. The first line of each
test case contains an integer *n* (0 <= *n* < 100)
that represents the number of mixtures in the test case. The next
*n* lines each contain three non-negative integers
*a*_{i}, *b*_{i},
*c*_{i}, specifying the ratio
*a*_{i} : *b*_{i} : *c*_{i}
in which A, B, C occur in the *i*^{th} mixture. At
least one of these integers is positive for each mixture.
Finally, there is one line containing three non-negative integers
*a*, *b*, *c*, which specify the ratio
*a* : *b* : *c* in the
desired solution. At least one of these integers is positive.

The input file is terminated with the integer 0 on a line by itself
foll owing the last test case.

### Output

For each test case, output the word `"Mixture"`

, followed
by the ordinal number of the test case. On the next line, if it is
possible to obtain the desired solution by mixing the input solutions,
output the word `"Possible"`

. Otherwise, output the word
`"Impossible"`

.

### Sample Input

2
1 2 3
3 7 1
3 4 5
3
1 2 3
3 7 1
2 1 2
3 4 5
0

### Output for the Sample Input

Mixture 1
Impossible
Mixture 2
Possible

This page maintained by
Ed Karrels.

Last updated September 8, 1999