用户 ainta 有排列 p1, p2, ..., pn。新年即将到来,他想让自己的排列尽可能漂亮。
排列 a1, a2, ..., an 比排列 b1, b2, ..., bn 更漂亮,当且仅当存在整数 k (1 ≤ k ≤ n),其中 a1 = b1, a2 = b2, ..., ak - 1 = bk - 1 且 ak < bk 均成立。
众所周知,排列 p 非常敏感,只能通过交换两个不同的元素来修改它。但交换两个元素比你想象的要困难。给定一个 n × n 二进制矩阵 A,当且仅当 Ai、j = 1 时,用户 ainta 可以交换 pi 和 pj 的值 (1 ≤ i, j ≤ n, i ≠ j)。
给定排列 p 和矩阵 A,用户 ainta 想知道他可以获得的最漂亮的排列。
输入
第一行包含一个整数 n (1 ≤ n ≤ 300) — 排列 p 的大小。
第二行包含 n 个空格分隔的整数 p1, p2, ..., pn — 用户 ainta 拥有的排列 p。 1 到 n 之间的每个整数在给定排列中只出现一次。
接下来的 n 行描述矩阵 A。第 i 行包含 n 个字符“0”或“1”,描述 A 的第 i 行。第 i 行 Ai,j 的第 j 个字符是 A 第 i 行和第 j 列交集上的元素。保证对于所有整数 i,j,其中 1 ≤ i < j ≤ n,Ai,j = Aj,i 成立。此外,对于所有整数 i(其中 1 ≤ i ≤ n),Ai, i = 0 成立。
输出
在第一行也是唯一一行中,打印 n 个空格分隔的整数,描述可以获得的最漂亮的排列。
示例
输入 #1
7 5 2 4 3 6 7 1 0001001 0000000 0000010 1000001 0000000 0010000 1001000
输出 #1
1 2 4 3 6 7 5
输入 #2
5 4 2 1 5 3 00100 00011 10010 01101 01010
输出 #2
1 2 3 4 5
注意
在第一个示例中,获得最漂亮的排列所需的交换是:(p1, p7)。
在第二个示例中,获得最漂亮的排列所需的交换是 (p1, p3)、(p4, p5)、(p3, p4)。
排列 p 是整数 p1, p2, ..., pn 的序列,由 n 个不同的正整数组成,每个不超过 n。排列 p 的第 i 个元素表示为 pi。排列 p 的大小表示为 n。