题目描述

用户 ainta 有一个排列 $p_1,p_2,...,p_n$。新年到了，他希望把他的排列变得尽可能漂亮。

当且仅当存在整数 $k$（$1 \le k \le n$）使 $a_1=b_1,a_2=b_2,\ldots,a_{k-1}=b_{k-1}$ 和 $a_k<b_k$ 都成立，排列 $a_1,a_2,...,a_n$ 比 $b_1,b_2,...,b_n$ 更漂亮。

排列 $p$ 非常敏感，只可以通过交换两个不同的元素来修改它。但是交换两个不同的元素比你想象得要难。给出一个 $n\times n$ 的二进制矩阵 $A$，当且仅当 $A_{i,j}=1$ 时，用户 ainta 可以交换两个元素 $p_i,p_j\ (1\le i,j\le n,i\neq j)$ 的值。

给定排列 $p$ 和矩阵 $A$ ，用户 ainta 想知道他能得到的最漂亮的排列。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 300$），即排列 $p$ 的长度。

第二行包含 $n$ 个由空格分开的整数 $p_1,p_2,...,p_n$ ，保证每个不同的整数只出现一次。

接下来 $n$ 行描述矩阵 $A$ 。保证 $A_{i,j}=A_{j,i}$（$1 \le i<j \le n$）和 $A_{i,i}=0$（$1 \le i \le n$）。

输出格式

一行 $n$ 个空格分隔的整数，表示得到的最漂亮的排列。

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