题目描述

小 A 有一张 $2\times n$ 行，$2\times m$ 列的表格。表格上每一行、每一列都有一个正整数。他将对表格先进行一次合并操作，再进行一次转置操作。

对于一个 $2\times n$ 行，$2\times m$ 列的表格 $A$，进行一次合并操作得到一个 $n$ 行 $m$ 列的表格 $A'$ 的流程为：

• 将奇数列的每个数加上其右侧相邻的数，之后删除所有的偶数列，给每一列重新编号为第 $1,2,3,\dots,m$ 列；
• 将奇数行的每个数加上其下侧相邻的数，之后删除所有的偶数行，给每一行重新编号为第 $1,2,3,\dots,n$ 行。

对于一个 $n$ 行 $m$ 列的表格 $A$，进行一次转置操作得到一个 $m$ 行 $n$ 列的表格 $A^T$ 的流程为：

• 对于所有的 $i,j$，令 $A^T_{i,j}=A_{j,i}$。

小 A 想要知道经过这样两次操作后表格会是什么样的。请输出该表格。

本题的输入输出规模较大，特别是对使用 Java/Python 等非传统语言的选手，请使用相对快速的输入输出方式。

输入格式

第一行输入两个正整数 $n$ 和 $m$。

第二行到第 $2\times n+1$ 行，每行输入 $2\times m$ 个正整数，表示表格上每一行每一列的值。

输出格式

输出一个 $m$ 行 $n$ 列的表格，表示经过两次操作后表格会是什么样的。同一行内的正整数之间用空格隔开。

样例 #1

样例输入 #1

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

样例输出 #1

18 18
19 13

样例 #2

样例输入 #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

样例输出 #2

12 25 17
13 24 16
12 23 18

提示

样例解释

对于样例 1，先把相邻两列两两相加并删除偶数列，再把相邻两行两两相加并删除偶数行，最后转置：

1. 删除偶数列后，每一行变成相邻两个数之和：第一行 $2+7=9,\ 1+8=9$，第二行 $1+8=9,\ 2+8=10$，第三行 $3+1=4,\ 4+1=5$，第四行 $5+9=14,\ 2+6=8$；
2. 删除偶数行后（奇数行加上其下侧相邻行）：第一行 $9+9=18,\ 9+10=19$，第二行 $4+14=18,\ 5+8=13$；
3. 转置后得到两行两列的结果。

实际上每一步都可以直接看成把原表中相邻 $2\times 2$ 的四个数相加：结果第 $i$ 行第 $j$ 列的数，就是原表第 $2i-1,2i$ 行与第 $2j-1,2j$ 列交叉的 $2\times 2$ 方块之和：

$$A''_{i,j}=A_{2i-1,2j-1}+A_{2i-1,2j}+A_{2i,2j-1}+A_{2i,2j}$$

样例 1 中四个 $2\times 2$ 方块的和分别为 $18,19$ 与 $18,13$，转置后即为：

18 18
19 13

数据规模与约定

对于所有数据，保证：$1 \leq n,m \leq 1000$，$1 \leq a_i \leq 10^6$。