Maximizing Linear Objective with Two Equality Constraints

You are given three sequences of n positive integers:

• \(A_1, A_2, \ldots, A_n\)
• \(B_1, B_2, \ldots, B_n\)
• \(C_1, C_2, \ldots, C_n\)

Then, you are given m queries. Each query provides two positive integers \(S\) and \(T\). For each query, find a set of nonnegative real numbers \(X_1, X_2, \ldots, X_n\) satisfying the system:

[ \begin{cases} A_1X_1 + A_2X_2 + \cdots + A_nX_n = S,\ B_1X_1 + B_2X_2 + \cdots + B_nX_n = T,\ X_i \ge 0 \quad \text{for } i=1,2,\ldots,n \end{cases} ]

Among all nonnegative solutions, choose one that maximizes the objective function:

[ C_1X_1 + C_2X_2 + \cdots + C_nX_n ]

If there is no valid solution, output -1. Otherwise, for each query, print a solution vector \(X_1, X_2, \ldots, X_n\) in one line, with each value rounded to 6 decimal places.

Note: It can be shown that an optimal solution (if one exists) can be found among the extreme points of the feasible region, i.e. at most two variables will be nonzero.

inputFormat

The first line contains two integers n and m separated by a space.

The second line contains n positive integers \(A_1, A_2, \ldots, A_n\) separated by spaces.

The third line contains n positive integers \(B_1, B_2, \ldots, B_n\) separated by spaces.

The fourth line contains n positive integers \(C_1, C_2, \ldots, C_n\) separated by spaces.

Then follow m lines, each containing two positive integers \(S\) and \(T\) separated by a space representing a query.

outputFormat

For each query, if a valid nonnegative solution exists, output a line with n real numbers \(X_1, X_2, \ldots, X_n\) rounded to 6 decimal places and separated by spaces, which yields the maximum value of \(C_1X_1 + C_2X_2 + \cdots + C_nX_n\). If no solution exists, output -1.

sample

3 3
1 2 3
2 3 4
3 2 1
5 8
6 9
3 5

1.000000 2.000000 0.000000
0.000000 3.000000 0.000000
1.000000 1.000000 0.000000

</p>