沙漠之旅（travel）

题目描述

大样例：travel.zip

小 D 最近到沙漠上去做考察。一提及沙漠，第一印象自然是热，炎热。因此小 D 的任务是勘测每个位置的“缺水度”。

我们可以将沙漠抽象成一个 $n\times m$ 的 $01$ 矩阵，第 $i$ 行第 $j$ 列的位置即为 $a_{i,j}$。

若 $a_{i,j}=1$，在意味着这块地上有水。一个点 $(x,y)$ 的“缺水度”为离它最近的有水的地，这里定义距离为两点的欧几里得距离的平方。

注：两个点 $(x_a,y_a)$ 和 $(x_b,y_b)$ 的欧几里得距离为 $\sqrt{(x_a-x_b)^2+(y_a-y_b)^2}$。

当然，作为一位地质学家，小 D 想要在四面八方均勘测这块地，因此我们需要求 $(x,y)$ 上下左右四个方向的“缺水度”。比如上方向的“缺水度”定义为满足 $a_{i,j}=1$ 且 $i\le x$ 的离 $(x,y)$ 最近的距离，下方向即 $i\ge x$，左方向即 $j\le y$，右方向即 $j\ge y$。

现在，你需要对于每块地，均计算出他们四个方向的“缺水度”，记为 $\operatorname{up}_{x,y},\operatorname{down}_{x,y},\operatorname{left}_{x,y},\operatorname{right}_{x,y}$，注意如果该方向不存在水源，那么“缺水度”定义为 $10^9$。

输入格式

第一行，输入两个数 $n,m$。

接下来 $n$ 行，每行输入 $m$ 个数，表示这个 $a$ 矩阵。

输出格式

为了减少输出量（因为有 $4nm$ 条信息），所以采用如下方式压缩输出：

输出 $4$ 个数，顺序依次是 $\operatorname{up},\operatorname{down},\operatorname{left},\operatorname{right}$，第 $1$ 个数表示

$$\bigoplus_{1\le i\le n,\,1\le j\le m}\operatorname{up}_{i,j},$$

其他同理。

样例 1

5 5
1 0 0 1 0
0 0 1 0 0
0 1 0 0 1
0 0 0 0 1
0 0 1 1 1

6 1 26 0

样例 2

3 3
0 0 0
0 0 0
0 0 0

1000000000 1000000000 1000000000 1000000000

备注

本题共 $10$ 组数据。

对于 $10\%$ 的数据，$1\le n,m\le100$；

对于 $30\%$ 的数据，$1\le n,m\le600$；

对于 $60\%$ 的数据，$1\le n,m\le1000$；

对于 $100\%$ 的数据，$1\le n,m\le4000$。

注意：数据量很大，可能需要高效的读入方式。