题目描述

有一个 $n$ 行 $m$ 列的房间网格，房间坐标为 $(i,j)$，其中 $(1,1)$ 位于左上角。

每个房间的上、右、下、左四面墙上可能有门。用整数 $a_{i,j}$ 表示房间 $(i,j)$ 的门：

$a_{i,j}$ 等于该房间所有门对应数值之和。例如，$a_{i,j}=6$ 表示这个房间有右门和下门。

两个相邻房间之间可以通行，当且仅当它们在相接的两面墙上都有门。网格边界上的门通向网格外。

巡检车从网格上方经过 $(1,1)$ 的上门进入房间 $(1,1)$。每当它从一扇门进入一个房间后，可以选择另一扇门离开，但不能立即从刚刚进入的门原路离开。若选择的门通向相邻房间，还需要两个房间在相接处都有门；巡检车随后从相邻房间的对应门进入。若选择的门通向网格外，本次路线立即结束。

巡检车可以多次进入同一个房间，也可以多次经过同一扇门。一条路线必须包含有限次移动。

当且仅当路线最终从房间 $(n,m)$ 的下门离开网格时，这条路线是成功路线。从其他边界门离开，或者在房间内无法继续移动，都不算成功。

如果至少存在一条成功路线经过房间 $(i,j)$，则称这个房间是可巡检的。

请判断每个房间是否可巡检。

输入格式

从文件 duct.in 中读取数据。

第一行包含两个整数 $n,m$。

接下来 $n$ 行，每行包含 $m$ 个整数。第 $i$ 行的第 $j$ 个整数为 $a_{i,j}$。

输出格式

输出到文件 duct.out 中。

输出 $n$ 行，每行一个长度为 $m$ 的字符串。

第 $i$ 行第 $j$ 个字符应为：

• 若房间 $(i,j)$ 可巡检，输出字符 1；
• 否则输出字符 0。

2 2
7 12
3 5

11
01

1 1
5

1

样例解释

样例 #1 中存在如下成功路线：

1. 从上方进入 $(1,1)$，再从右门进入 $(1,2)$；
2. 从 $(1,2)$ 的下门进入 $(2,2)$；
3. 从 $(2,2)$ 的下门离开网格。

若路线经过 $(2,1)$，巡检车只能从它的上门进入。此时不能立即从上门返回，而它的右门与 $(2,2)$ 的左墙不连通，因此不存在经过 $(2,1)$ 的成功路线。

样例 #2 中，巡检车从唯一房间的上门进入，再从下门离开。

数据规模与约定

对于所有数据，保证：

• $1\le n,m\le 2\times 10^5$；
• $1\le n\times m\le 2\times 10^5$；
• 对于 $1\le i\le n,\ 1\le j\le m$，有 $0\le a_{i,j}\le 15$；
• $a_{1,1}$ 表示的门中包含上门；
• $a_{n,m}$ 表示的门中包含下门。

本题采用子任务捆绑计分。只有通过某个子任务内的所有测试点，才能获得该子任务的分数。各子任务独立计分。

下发文件

下载三组测试数据，非真实测试数据