/ 
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_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
もとのグラフとしてありうるものは存在しません。