题目描述

给定一个两侧各有$n$和$m$个点的二分图（保证$n≤m$），对于每条边，你需要判断原图是否存在一个大小为$n$，且包含了这条边的匹配。

输入

第一行两个整数$n，m$。 接下来$n$行，每行一个长度为$m$的字符串，对于第$i + 1$行的第$j$个字符，如果它是$1$，则左侧的点$i$与右侧的点$j$之间存在连边，否则不存在。

输出

输出$n$行，每行一个长度为$m$的字符串，对于左侧的点$i$与右侧的点$j$，如果不存在一组大小为$n$的匹配包含它们之间的连边，或它们之间没有连边，则第i行的第$j$个字符应为 $1$，否则为$0$。

输入样例

4 4
1111
1000
1111
1111

输出样例

1000
0111
1000
1000

提示

【样例输入2】

4 5
10000
10000
10000
10000

【样例输出2】

11111
11111
11111
11111

【样例输入3】

4 4
1111
1110
1100
1000

【样例输出3】

1110
1101
1011
0111

【数据规模】 对于50%的数据，$1≤n≤15，1≤m≤30$； 对于100%的数据，$1≤n≤300，1≤m≤1500$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。