该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

C.排列交换

小聪有一个排列 $p_1, p_2, \dots, p_n$。

小聪觉得小小的排列比较可爱，他希望把这个排列字典序变得尽量小。

这个问题太简单了，小聪的朋友小潘决定给他上点强度。

小潘给出了一个大小为 $n\times n$ 的对称 01 矩阵 $A$。小潘命令小聪只能交换满足 $A_{i,j}=1$ 的 $p_i$ 和 $p_j$。交换的顺序和次数都不限。

小聪想知道，在小潘的要求下，他的排列最小能是多少。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个数 $p_1, p_2, \dots, p_n$ 表示排列。

接下来 $n$ 行描述矩阵 $A$。

输出格式

输出一行，表示字典序最小的排列。

样例输入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

数据范围

对于 $40\%$ 的数据，$1 \leq n \leq 11$。

对于 $70\%$ 的数据，$1 \leq n \leq 20$。

对于 $100\%$ 的数据，$1 \leq n \leq 300$，保证 $A$ 是对称矩阵且对角线为 $0$。