配点 : 400 点
問題文
高桥君来自青木君,3N 我收到了一个由顶点组成的有向图。 在此图的顶部, 它被命名为x_0,x_1,\cdots,x_{N-1},y_0,y_1,\cdots,y_{N-1},z_0,z_1,\cdots,z_{N-1} 。 该图的所有边都是 从x 的顶点开始 朝向 y 顶点的边,或 这是通往y 的顶点开始 朝向 z 顶点的边。 请注意,没有多重边。
当高桥正在玩这个图表时,2N 长度 我得到了 N 字符串 A_0,A_1,\cdots,A_{N-1},B_0,B_1,\cdots,B_{N-1} 。 这些字符串具有以下属性:
- A_i 的 j 文字目 (0 \leq i,j \leq N-1)是
顶点 x_i 到顶点
当有一个边沿走向 y_j 时
1,如果不存在 当存在通往0。 - B_i 的 j 文字目 (0 \leq i,j \leq N-1)是
顶点 x_i 到顶点
当有一个边沿走向 z_j 的路径时
1,如果不存在 当存在通往0。
高桥君不小心毁掉了这张图,但是上面的 我记得 2N 字符串。 除了高桥君以外,原图可能是什么? 1 请注明之一。 不过,如果高桥君记忆有误,没有可能的原图,请指出。 长度由
制約
- 1 \leq N \leq 300
- A_i 是
仅由
0,1组成 它是一个 N 字符串。 - B_i 是
仅由
0,1组成 它是一个 N 字符串。
入力
输入是按以下格式从标准输入给出的。
N
A_0
A_1
\vdots
A_{N-1}
B_0
B_1
\vdots
B_{N-1}
出力
如果没有可能的原始图, 输出-1 。
如果有可能的原始图,y 的顶点开始 朝向 z 顶点的边。
c_{0,0}c_{0,1}\cdots c_{0,N-1}
c_{1,0}c_{1,1}\cdots c_{1,N-1}
\vdots
c_{N-1,0}c_{N-1,1}\cdots c_{N-1,N-1}
在这里,c_{i,j} 是y_i 从 z_j 时 1,如果不存在
当存在通往 0 。
如果有多个解,则任何输出都将被确定为正确答案。
入力例 1
3 010 001 101 110 010 011
出力例 1
011 110 010
比如,根据高桥君的记忆,最上面 有一条通往 x_2 到顶点 当有一个边沿走向 z_1 的路径,但是 示例输出图包含 存在名为x_2 → y_2 → z_1 的路径。
入力例 2
3 010 001 101 110 010 001
出力例 2
-1
没有可能的原始图表。