シーケンスを最小化する (Minimize the Sequence)

与えられた n 個の数 からなるシーケンスを、できるだけ辞書式順 (lexicographically) で小さくしてください。辞書式順で小さくするには、シーケンス内の 許可された 要素同士を入れ替える (swap) 操作を行います。入れ替えは何度でも行えますが、すべての要素が自由に入れ替えられるわけではなく、入れ替えが許可されている特定のインデックス同士のみが操作可能です。

このとき、入れ替え可能な位置関係を示す行列が与えられています。初期シーケンスから、可能な操作を使って得られるシーケンスの中で、辞書式順がもっとも小さいものを出力してください。

入力

1行目には整数 n (1 ≤ n ≤ 300) が与えられます。

2行目には、空白区切りで n 個の整数 (1 ≤ ≤ n) が与えられます。これは初期シーケンスを表し、数値はすべて異なります。

続く n 行には、各行に n 個の 0 または 1 が与えられます。行 i 列 j の値が 1 のときは、i 番目と j 番目の要素同士の入れ替えが許可されていることを意味し、0 の場合は入れ替えが許可されていないことを意味します。

出力

与えられた初期シーケンスから、入れ替え操作によって作ることができる辞書式順でもっとも小さいシーケンスを出力してください。

例

解説

1. 以下のような入れ替え操作が可能です:

   1. ↔  ⇒ 1 2 4 5 3

   2. ↔  ⇒ 1 2 4 3 5

   3. ↔  ⇒ 1 2 3 4 5

2. ↔ ⇒ 1 2 4 5 3