Feed Mixture Ratio

Given three types of feed, each with a ratio of barley, oats, and wheat components, determine the way to mix these feeds to produce a target feed with ratio \(x:y:z\). Specifically, the first feed has ratio \(a_1:b_1:c_1\), the second feed has ratio \(a_2:b_2:c_2\), and the third feed has ratio \(a_3:b_3:c_3\). You are also given the target ratio \(x:y:z\). You need to find nonnegative integers \(f_1\), \(f_2\), \(f_3\) (not all zero) such that

[ \begin{aligned} &a_1 f_1 + a_2 f_2 + a_3 f_3 = k \times x, \ &b_1 f_1 + b_2 f_2 + b_3 f_3 = k \times y, \ &c_1 f_1 + c_2 f_2 + c_3 f_3 = k \times z, \end{aligned} ]

for some positive integer \(k\). Among all possible solutions, choose the one with the minimum total feed count \(f_1 + f_2 + f_3\). If no such combination exists, output a single line containing the string NONE.

For example, if the three feeds have ratios 1:2:3, 3:7:1, and 2:1:2 respectively and the target ratio is 3:4:5, one valid solution is to use 8 portions of the first feed, 1 portion of the second feed, and 5 portions of the third feed, which yields:

[ \begin{aligned} &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. \end{aligned} ]

Since \(21:28:35 = 3:4:5\) (with \(k=7\)) and the total amount \(8+1+5=14\) is minimized, the program should output: 8 1 5 7 (the first three numbers indicate the feed counts and the fourth number is the multiplier \(k\)).

inputFormat

The input consists of four lines. Each of the first three lines contains three integers representing the ratios of barley, oats, and wheat in the feed types 1, 2, and 3 respectively. The fourth line contains three integers \(x\), \(y\), and \(z\) representing the target ratio \(x:y:z\). The integers on each line are separated by spaces.

outputFormat

If a solution exists, output one line containing four integers separated by a space: \(f_1\), \(f_2\), \(f_3\), and \(k\). Otherwise, output a single line with the string NONE.

sample

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

8 1 5 7