Matrix Merge and Transpose

You are given a matrix with 2n rows and 2m columns. Each cell contains a positive integer. First, you perform a merge operation on the matrix, and then you transpose the result.

The merge operation on a 2n × 2m matrix A produces an n × m matrix A' as follows:

• Column Merge: For each row, for every odd-indexed column j (1-indexed), add the number in that column with its right neighbor (i.e. add A_{i, j} + A_{i, j+1}). Then, remove all even-indexed columns and renumber the remaining columns as 1, 2, …, m.
• Row Merge: After the column merge, for every odd-indexed row i (1-indexed), add the numbers with the number in the row immediately below (i.e. add A'_{i, j} + A'_{i+1, j}). Then, remove all even-indexed rows and renumber the remaining rows as 1, 2, …, n.

Thus, every cell in the merged matrix A' is given by:

\( A'_{i,j} = (A_{2i-1,2j-1} + A_{2i-1,2j}) + (A_{2i,2j-1} + A_{2i,2j}) \)

Finally, you transpose the matrix A' to obtain matrix A^T of dimension m × n such that for all valid i, j:

\( A^T_{i,j} = A'_{j,i} \)

Output the final matrix A^T.

Note: The input size can be large, so please use fast input/output methods in languages like Java and Python.

inputFormat

The first line contains two integers n and m.

Then, there are 2n lines, each containing 2m integers, representing the matrix.

Constraints:

• 1 ≤ n, m ≤ 1000 (or as specified)
• All numbers are positive integers.

outputFormat

Output the transposed matrix A^T having m rows and n columns. Each of the m lines should contain n integers separated by spaces.

sample

1 1
1 2
3 4

10