问题背景

我们称一个大小为 $n$ 的数列 $p_1, p_2, \ldots, p_n$ 是一个排列，当且仅当整数 $1 \sim n$ 在排列 $p$ 中均出现恰好一次。比如：

• $[1, 2, 3, 4]$ 是一个大小为 $4$ 的排列；
• $[5, 3, 2, 4, 1, 6, 7]$ 是一个大小为 $7$ 的排列；
• $[2]$，$[1, 3, 4, 3]$，$[1, 3, 4, 5, 6]$ 都不是排列。

对于两个大小为 $n$ 的排列 $p_1, p_2, \ldots, p_n$ 和 $q_1, q_2, \ldots, q_n$，若满足如下条件，则我们称排列 $p$ 的字典序小于排列 $q$：

• 存在一个下标 $i(1 \le i \le n)$，满足 $p_i \lt q_i$；
• 对于任意下标 $1 \le j \lt i$，均有 $p_j = q_j$。

比如，排列 $[1, 3, 2, 4]$ 的字典序小于排列 $[2, 1, 4, 3]$；排列 $[3, 4, 5, 6, 1, 2]$ 的字典序小于排列 $[3, 4, 5, 6, 2, 1]$。

题目描述

给定一个大小为 $n$ 的数列 $p_1, p_2, \ldots, p_n$。

你可以交换排列中一些元素的数值，但是这受到规则的限制。

规则被描述为一个 $n \times n$ 的01矩阵 $A$，我们用 $A_{i,j}$ 表示矩阵 $A$ 中第 $i$ 行第 $j$ 的元素，则：

• 若 $A_{i,j} = 1$，则你可以交换 $p_i$ 和 $p_j$ 的数值；
• 若 $A_{i,j} = 0$，则你不能交换 $p_i$ 和 $p_j$ 的数值。

你可以对排列 $p$ 进行任意次操作，每次操作，你可以选择可以交换数值的两个元素并交换它们的数值。

你希望通过若干次操作使排列 $p$ 的字典序最小。

输入格式

第一行包含一个整数 $n(1 \le n \le 1000)$，表示排列的大小。

第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n(1 \le p_i \le n)$，表示一个大小为 $n$ 的排列。

接下来 $n$ 行，每行包含一个长度为 $n$ 的仅由 $0$ 和 $1$ 构成的字符串。表示 01矩阵 $A$。

输出格式

输出共一行，包含 $n$ 个整数，两两之间以一个空格分隔，表示你能够得到的字典序最小的排列 $p$。

7
5 2 4 3 6 7 1
0001001
0000000
0000010
1000001
0000000
0010000
1001000

1 2 4 3 6 7 5

5
4 2 1 5 3
00100
00011
10010
01101
01010

1 2 3 4 5

说明/提示

样例解释

样例1：只需要交换 $(p_1, p_7)$；

样例2：依次交换 $(p_1, p_3), (p_4, p_5), (p_3, p_4)$

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 10$
• 对于 $50\%$ 的数据，$n \le 100$
• 对于 $100\%$ 的数据，$1 \le n \le 1000$，$p$ 是一个大小为 $n$ 的排列，$0 \le A_{i, j} \le$，且对于任意 $i \neq j$ 均有 $A_{i,j} = A_{j,i}$，且对于任意 $1 \le i \le n$ 均有 $A_{i,i} = 0$