Kevin wants a "perfect matrix" with rows and
columns.
He has certain expectations for some matrix that he considers perfect.
He has a desired integer range for each element of , as well as a desired integer range for each row sum and column sum.
More formally, given other
matrices
and
, and matrices
and
of dimensions
and
respectively, all of the following conditions must hold:
for all (
for all
for all
Help Kevin find any perfect matrix or determine that it is impossible to do so.
Constraints
Input Specification
The first line of input contains integers and
.
The next lines of input each contain
space-separated integers representing the matrix
, the minimum values of each element.
The next lines of input each contain
space-separated integers representing the matrix
, the maximum values of each element.
The next lines of input each contain
space-separated integers representing the matrix
, the minimum and maximum sums of each row.
The next lines of input each contain
space-separated integers representing the matrix
, the minimum and maximum sums of each column.
Output Specification
Output lines of
space-separated integers representing any perfect matrix that satisfies Kevin or report that it is impossible to do so by outputting
-1
.
Sample Input
2 2
3 0
0 3
3 9
9 3
5 5
1 6
6 9
0 9
Sample Output
3 2
3 3
Explanation for Sample
In the example above, this is the only matrix that Kevin will consider perfect.
Comments