时间限制： 1.0 秒

空间限制： 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\limits_{i=1}^n|a_i−b_i|$，即 $|a_1−b_1|+|a_2−b_2|+\cdots+|a_n−b_n|$，为这两个点的（曼哈顿）距离。

容易看出，两个点的距离至少为 $0$，至多为 $n \cdot (m−1)$。

$m^n$ 个点中的每个点都具有一个权值。

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

输入格式

从标准输入读入数据。

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

接下来 $m^n$ 行，每行一个正整数，表示每个点的权值。

输入是按照坐标序列的字典序排列的，即先输入点 $(1,1,\cdots,1,1)$ 的权值，再输入 $(1,1,\cdots,1,2)$ 的权值，$\cdots$，再输入 $(1,1,\cdots,1,m)$ 的权值，再输入 $(1,1,\cdots,2,1)$ 的权值 $\cdots$ 。

输出格式

输出到标准输出。

输出 $m^n$ 行，每行表示一个点。

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

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

3 2
1
2
4
8
16
32
64
128

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 3
9
8
7
6
5
4
3
2
1

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 \ge 1,~m \ge 2$，要输出的数不会超过 $1.25 \times 10^6$ 个。每个点的权值不会超过 $10^5$。

提示

本题输入输出量较大，请采用效率较高的输入输出方式。