Description

Given three sets of integers, each set represents the ratio of barley, oats, and wheat in one feed. Find a way to blend these three feeds to obtain a feed with ratio $x:y:z$.

Write a program to find the solution that minimizes the total amount of the three feeds used. If it is impossible to obtain the target feed from these three feeds, output a single line containing the string NONE. “Minimum amount” means the sum of the amounts (integers) of the three feeds must be minimized.

For example, if we want to use feeds with ratios $1:2:3$, $3:7:1$, and $2:1:2$ to produce a feed with ratio $3:4:5$, we can blend $8$ units of the first feed, $1$ unit of the second feed, and $5$ units of the third feed to obtain $7$ units of the target feed. This is because $8 \times 1 + 1 \times 3 + 5 \times 2 = 21$, $8 \times 2 + 1 \times 7 + 5 \times 1 = 28$, $8 \times 3 + 1 \times 1 + 5 \times 2 = 35$, and $21:28:35$ is exactly equal to $3:4:5$.

Input Format

The first line contains three integers $x, y, z$, indicating that the target feed has barley, oats, and wheat in the ratio $x:y:z$.

The next three lines, the $i$-th line contains three integers $a_i, b_i, c_i$, indicating that the $i$-th feed has barley, oats, and wheat in the ratio $a_i:b_i:c_i$.

All integers in the input are between $0$ and $99$ inclusive, and in each line the three integers are not all $0$.

Output Format

If the target feed can be obtained by blending the three feeds, output one line with $4$ integers. The first three integers $m, n, p$ represent the portions of the three feeds, and the fourth integer represents the number of portions of the target feed obtained. If there are multiple solutions, output the one with the smallest $m+n+p$. If the target feed cannot be obtained from the three feeds, output a single line containing the string NONE. It is guaranteed that if a solution exists, the solution with the smallest $m+n+p$ is unique.

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

8 1 5 7

Hint

Translation from NOCOW. USACO Training Section 3.2.

Translated by ChatGPT 5