Witches

Three witches are brewing potions around their cauldron when they notice that someone has mixed up all n of their carefully crafted potions. Each potion is a carefully-measured mixture of exact ratios of m distinct individual components (e.g. eye of newt, etc.). Mixed together, even though the components are the same, the ratios of the potions are now all wrong and will not have the desired effect.

Luckily, the vials in which the potions are kept are bottomless. In theory, the witches have an unbounded amount of each of the messed-up potions.

There is one potion in particular that the witches are interested in making so they need to combine the potions that they have into their cauldrons so as to come up with the correct ratio for it.

Consider the following example where n = 2 and m = 3: Two potions are available with the ratios of 1:2:3 and 3:7:1, respectively. By mixing those two solutions together in the ratio 1:2, it is possible to obtain a solution of the m = 3 components with ratio 7:16:5, but there is no way to combine these two potions together into a new one with ratio 3:4:5. However, if the witches find another potion with ratio 2:1:2 (making the problem into one where n = 3), then a 3:4:5 mixture is possible with eight parts of 1:2:3, one part 3:7:1, and 5 parts of 2:1:2.

So clearly, determining which mixtures can be obtained from a given set of potions is not trivial. It is your goal in this assignment to do so.

Input/Output

The top line of the input file (input.txt) will be a line with a desired ratio in the form a₁ : a₂ : a₃ : : a_m. The next n lines will be the base solution ratios.

Your output file (output.txt) will consists of n lines, each containing a single integer. These will indicate the parts necessary to get the desired ratio. If no combination is possible, then return the value 1 on each line.

1

So, for example above, the input file (input.txt) would look as follows:

3:4:5

1:2:3

3:7:1

2:1:2 and the output file (output.txt) would look as follows:

8

1

5

2