给定一个包含 $n$ 个顶点的无向图。对于每一对顶点 $(i, j)$ ($i \neq j$)，确定是否存在一条从 $i$ 出发并以 $j$ 结尾的哈密顿路径。

回想一下，哈密顿路径是指一条包含 $n-1$ 条边，且恰好经过所有顶点一次的路径。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 24$)，表示图中的顶点数。

接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $n$ 的二进制字符串 $s_i$。其第 $i$ 个字符始终为 $0$；对于 $j \neq i$，若顶点 $i$ 和 $j$ 之间存在边，则第 $j$ 个字符为 $1$，否则为 $0$。

保证对于任意 $i \neq j$，第 $j$ 行的第 $i$ 个字符与第 $i$ 行的第 $j$ 个字符相同。

输出格式

输出 $n$ 行。在第 $i$ 行中，输出一个长度为 $n$ 的二进制字符串。其第 $i$ 个字符必须为 $0$；对于 $j \neq i$，若存在一条从顶点 $i$ 到顶点 $j$ 的哈密顿路径，则第 $j$ 个字符为 $1$，否则为 $0$。

样例

输入 1

4
0110
1010
1101
0010

输出 1

0001
0001
0000
1100

输入 2

6
010001
101000
010100
001010
000101
100010

输出 2

010001
101000
010100
001010
000101
100010

输入 3

4
0111
1011
1101
1110

输出 3

0111
1011
1101
1110

说明

在第一个样例中，哈密顿路径存在于顶点对 $(1, 4)$ 和 $(2, 4)$ 之间。

在第二个样例中，该图是一个长度为 $6$ 的环。这里的哈密顿路径仅存在于相邻的顶点对之间。

在第三个样例中，我们有一个包含 $4$ 个顶点的完全图。每一对顶点之间都存在哈密顿路径。