说明

有 $HW$ 把椅子排列成 $H$ 行 $W$ 列。我们将从上往下数第 $i$ 行、从左往右数第 $j$ 列的椅子记作 $(i, j)$。

一些椅子上可能放有行李。椅子的状况由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \ldots, S_H$ 表示。如果 $S_i$ 的第 $j$ 个字符是 #，则表示 $(i, j)$ 上有行李。如果是 .，则表示 $(i, j)$ 上没有行李。保证至少有一把椅子上没有行李。

我们想安排人们坐在这些椅子上。每把椅子最多只能坐一个人，且人不能坐在放有行李的椅子上。此外，两个人不能坐在垂直或水平方向上相邻的椅子上。在这些条件下，我们希望尽可能多地安排人就座。设 $M$ 为遵守这些规则所能安排的最大人数。

现在，假设又来了一个人。对于每把椅子，判断我们是否可以让这个人坐在那里。具体来说，判断是否可以让这个人坐在那把椅子上，并且在此之后，仍然能够按照规则再安排 $M - 1$ 个人就座。

输入格式

输入格式如下：

$$\begin{aligned} &H \ W \\ &S_1 \\ &S_2 \\ &\vdots \\ &S_H \end{aligned}$$

• $1 \leq H \leq 400$
• $1 \leq W \leq 400$
• $S_i$ 是一个长度为 $W$ 的字符串，由 # 和 . 组成（$1 \leq i \leq H$）。
• 存在 $(i, j)$ 使得 $S_i$ 的第 $j$ 个字符是 .。
• $H$ 和 $W$ 是整数。

输出格式

输出 $H$ 行。在第 $i$ 行（$1 \leq i \leq H$），输出一个长度为 $W$ 的字符串。

对于每个 $(i, j)$，如果我们可以让新来的人坐在 $(i, j)$ 上，则第 $i$ 行字符串的第 $j$ 个字符必须是 1。否则，必须是 0。

3 4
##..
....
#.##

0011
1011
0100

提示

翻译由 DeepSeek V3.2 完成