Problem Description

Xiao A has a table with $2 \times n$ rows and $2 \times m$ columns. Each row and each column in the table has a positive integer. He will first perform a merge operation on the table, followed by a transpose operation.

For a table $A$ with $2 \times n$ rows and $2 \times m$ columns, the process of performing a merge operation to obtain a table $A'$ with $n$ rows and $m$ columns is as follows:

• Add each number in the odd columns to its right adjacent number, then delete all even columns, and renumber each column as the 1st, 2nd, 3rd, ..., $m$-th column;
• Add each number in the odd rows to its lower adjacent number, then delete all even rows, and renumber each row as the 1st, 2nd, 3rd, ..., $n$-th row;

For a table $A$ with $n$ rows and $m$ columns, the process of performing a transpose operation to obtain a table $A^T$ with $m$ rows and $n$ columns is as follows:

• For all $i, j$, let $A^T_{i,j} = A_{j,i}$;

Xiao A wants to know what the table will look like after these two operations. Please output the table.

The input and output for this problem are large, especially for contestants using non-traditional languages like Java/Python, please use relatively fast input and output methods.

Input Format

The first line contains two positive integers $n$ and $m$.

From the second line to the $2 \times n + 1$-th line, each line contains $2 \times m$ positive integers, representing the values in each row and each column of the table.

Output Format

Output an $m$ by $n$ table, representing what the table will look like after the two operations. Positive integers within the same row should be separated by spaces.

Sample Input and Output

Sample Input #1

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

Sample Output #1

18 18
19 13

Sample Input #2

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

Sample Output #2

12 25 17
13 24 16
12 23 18

Notes

[Sample Explanation]

For the table given in Sample 1, it is obtained through these transformations:

$\begin{bmatrix}2 & 7 & 1 & 8 \\ 1 & 8 & 2 & 8 \\ 3 & 1 & 4 & 1 \\ 5 & 9 & 2 & 6 \end{bmatrix} \xrightarrow{delete columns} \begin{bmatrix} 9 & 9 \\ 9 & 10 \\4 & 5 \\ 14 & 8 \\\end{bmatrix} \xrightarrow{delete rows} \begin{bmatrix} 18 & 19 \\ 18 & 13\end{bmatrix} \xrightarrow{transpose} \begin{bmatrix} 18 & 18 \\19 & 13\end{bmatrix}$

[Data Range]

For all data, it is guaranteed that: $1 \leq n, m \leq 1000$, $1 \leq a_i \leq 10^6$.

见题面 Input 部分

见题面 Output 部分