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 weights 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 weights 7:16:5. But there is no way to combine these mixtures into a new one with weights 3:4:5. If we additionally had a solution of weights 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. As you see in both examples, weights for each component must be integers.
Determining which mixing weights we can obtain from a given set of solutions 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.
Finally, there is one line containing three non-negative integers a, b, c, which specify the weights a : b : c in the desired solution. At least one of these integers is not 0.
The input file is terminated with the integer `0' on a line by itself following the last test case.
2 1 2 3 3 7 1 3 4 5 3 1 2 3 3 7 1 2 1 2 3 4 5 0
Mixture 1 Impossible Mixture 2 Possible