有 $H \times W$ 把椅子，排列在 $H$ 行 $W$ 列中。我们用 $(i, j)$ 表示从上往下数第 $i$ 行、从左往右数第 $j$ 列的椅子。

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

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

现在，假设有一位新客人到来。对于每把椅子，判断我们是否可以将这位新客人安排在该椅子上就座。具体来说，判断是否可以将该客人安排在 $(i, j)$ 就座，并且在遵守规则的前提下，仍能安排另外 $M - 1$ 个人就座。

输入格式

输入按以下格式给出：

H W
S_1
S_2
...
S_H

数据范围

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

输出格式

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

对于每个 $(i, j)$，如果我们可以将新来的客人安排在 $(i, j)$ 就座，则第 $i$ 行字符串的第 $j$ 个字符必须为 1。否则，必须为 0。

样例

输入样例 1

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

输出样例 1

0011
1011
0100