## Singularity Cup P5 - Perfect Matrix

View as PDF

Points: 20
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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.

#### 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.