Prof. Pang's Pangland Division

In Pangland, a toroidal board of size \( n\times m \), each cell \( (i,j) \) is connected to its four neighbors with the additional wrap-around connectivity: cell \( (1,y) \) is adjacent to \( (n,y) \) and cell \( (x,1) \) is adjacent to \( (x,m) \) for all valid \( x,y \). Prof. Pang has three sons. The first, second, and third sons live in distinct cells \( (x_1,y_1) \), \( (x_2,y_2) \), and \( (x_3,y_3) \) respectively. He wants to partition the board among his sons such that:

• Each cell is assigned to exactly one son.
• The \( i\)-th son receives exactly \( cnt_i \) cells and his living cell is included.
• The cells assigned to each son form a connected region (connectivity is defined via shared edges on the toroidal board).

If such a division is possible, output one valid assignment; otherwise, output -1.

One way to guarantee connectivity is to first find a Hamiltonian cycle of the board. For boards with at least one even dimension, a snake-like traversal produces a Hamiltonian cycle. By rotating the cycle and partitioning it into three contiguous segments of lengths \( cnt_1 \), \( cnt_2 \), and \( cnt_3 \) (with \( cnt_1+cnt_2+cnt_3=n\times m \)), we obtain connected regions. However, we must ensure that the living cell of each son falls into the appropriate segment. In our solution, we compute a snake ordering of cells and then try all rotations to satisfy these conditions.

inputFormat

The first line contains two integers \( n \) and \( m \) representing the number of rows and columns of the board.

The second line contains three integers \( cnt_1 \), \( cnt_2 \), and \( cnt_3 \) (with \( cnt_1+cnt_2+cnt_3 = n\times m \)).

The next three lines each contain two integers. The \( i\)-th of these lines contains \( x_i \) and \( y_i \), the coordinates of the living cell for the \( i\)-th son.

outputFormat

If a valid assignment exists, output \( n \) lines, each containing \( m \) integers. The integer on the \( j\)-th position of the \( i\)-th line indicates the son number (1, 2, or 3) to whom cell \( (i,j) \) is assigned. If no valid assignment exists, output a single line containing -1.

sample

3 4 4 4 4
1 1
2 3
3 4

1 1 1 1
2 2 2 2
3 3 3 3