B - Reachability /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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_ij 文字目 (0 \leq i,j \leq N-1) は、 頂点 x_i から頂点 y_j へ向かう辺が存在するときは 1、存在しないときは 0 である。
  • B_ij 文字目 (0 \leq i,j \leq N-1) は、 頂点 x_i から頂点 z_j へ向かうパスが存在するときは 1、存在しないときは 0 である。

高橋くんはうっかりこのグラフを壊してしまいましたが、上述の 2N 個の文字列は覚えています。 高橋くんの代わりに、もとのグラフとしてありうるものを 1 つ示してください。 ただし、高橋くんの記憶が間違っており、もとのグラフとしてありうるものが存在しない場合は、そのように指摘してください。

制約

  • 1 \leq N \leq 300
  • A_i0,1 からなる長さ N の文字列である。
  • B_i0,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

もとのグラフとしてありうるものは存在しません。