**时间限制：** 1 秒 


**空间限制：** 512 MB

**相关文件：** 题目目录




## 题目描述

在很多领域下，我们需要将高维空间中的点作为某个模型的基本研究对象。

现在我们建立一个$n$维的直角坐标系，每个点可以用它的坐标$(x_1,x_2,\cdots,x_n)$来表示。如果我们设定每一维坐标都必须是不超过$m$的正整数，那么一共就有$m^n$个点。

对于两个点$(a_1,a_2,\cdots,a_n)$与$(b_1,b_2,\cdots,b_n)$，我们定义$\sum_{i=1}^n |a_i-b_i|$，即$|a_1-b_1|+|a_2-b_2|+\cdots+|a_n-b_n|$，为这两个点的（曼哈顿）距离。容易看出，两个点的距离至少为$0$，至多为$n(m-1)$。

$m^n$个点中的每个点都具有一个权值。你需要对于每个点，对于每个满足$0 \leq d \leq n(m-1)$的$d$，求出和这个点距离为$d$的所有点的权值之和。（如果不存在这样的点则应输出$0$）

## 输入格式

第一行输入两个正整数$n,m$，用空格隔开。

接下来$m^n$行，每行一个正整数，表示每个点的权值。输入是按照坐标序列的字典序排列的，即先输入点$(1,1,\cdots,1,1)$的权值，再输入$(1,1,\cdots,1,2)$的权值，……，再输入$(1,1,\cdots,1,m)$的权值，再输入$(1,1,\cdots,2,1)$的权值……

## 输出格式

输出$m^n$行，每行表示一个点。每行有$n(m-1)+1$个整数，依次表示和这个点距离为$0,1,\cdots,n(m-1)$的所有点的权值之和。

输出的点的顺序应与输入相同；同一行相邻的两个整数之间应当用恰好一个空格隔开。

**由于数据规模较大，输出规模可达上百万个整数，请务必使用快速的方式进行输入输出。**






## 样例1输入

```plain
3 2
1
2
4
8
16
32
64
128

```



## 样例1输出

```plain
1 22 104 128
2 41 148 64
4 73 146 32
8 134 97 16
16 97 134 8
32 146 73 4
64 148 41 2
128 104 22 1

```







## 样例2输入

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

```



## 样例2输出

```plain
9 14 15 6 1
8 21 12 4 0
7 12 15 8 3
6 17 14 8 0
5 20 20 0 0
4 13 16 12 0
3 8 15 12 7
2 9 18 16 0
1 6 15 14 9

```


## 测试点

所有数据满足：$n \geq 1, m \geq 2$，要输出的数不会超过$1250000$个。每个点的权值不会超过$100000$。

测试点1：$n=1,m=1000$。
测试点2：$n=2,m=85$。
测试点3：$n=3,m=25$。
测试点4：$n=4,m=12$。
测试点5：$n=5,m=8$。
测试点6：$n=6,m=5$。
测试点7：$n=8,m=3$。
测试点8：$n=10,m=3$。
测试点9：$n=13,m=2$。
测试点10：$n=16,m=2$。