← 返回题目列表

Codeforces · 500/B

B. 新年排列

中文机器翻译题面 查看原题

用户 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。