A9694 | New Year Permutation

User ainta has a permutation $p_{1},p_{2},...,p_{n}$ . As the New Year is coming, he wants to make his permutation as pretty as possible.

Permutation $a_{1},a_{2},...,a_{n}$ is prettier than permutation $b_{1},b_{2},...,b_{n}$ , if and only if there exists an integer $k$ ( $1<=k<=n$ ) where $a_{1}=b_{1},a_{2}=b_{2},...,a_{k-1}=b_{k-1}$ and $a_{k}<b_{k}$ all holds.

As known, permutation $p$ is so sensitive that it could be only modified by swapping two distinct elements. But swapping two elements is harder than you think. Given an $n×n$ binary matrix $A$ , user ainta can swap the values of $p_{i}$ and $p_{j}$ ( $1<=i,j<=n$ , $i≠j$ ) if and only if $A_{i,j}=1$ .

Given the permutation $p$ and the matrix $A$ , user ainta wants to know the prettiest permutation that he can obtain.

The first line contains an integer $n$ ( $1<=n<=300$ ) — the size of the permutation $p$ .

The second line contains $n$ space-separated integers $p_{1},p_{2},...,p_{n}$ — the permutation $p$ that user ainta has. Each integer between $1$ and $n$ occurs exactly once in the given permutation.

Next $n$ lines describe the matrix $A$ . The $i$ -th line contains $n$ characters '0' or '1' and describes the $i$ -th row of $A$ . The $j$ -th character of the $i$ -th line $A_{i,j}$ is the element on the intersection of the $i$ -th row and the $j$ -th column of A. It is guaranteed that, for all integers $i,j$ where $1<=i<j<=n$ , $A_{i,j}=A_{j,i}$ holds. Also, for all integers $i$ where $1<=i<=n$ , $A_{i,i}=0$ holds.

In the first and only line, print $n$ space-separated integers, describing the prettiest permutation that can be obtained.