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.


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 ai, bi, ci, specifying the ratio ai : bi : ci in which A, B, C occur in the ith 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.


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

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

Output for the Sample Input

Mixture 1

Mixture 2

This page maintained by Ed Karrels.
Last updated September 8, 1999