Description

User ainta has a permutation p₁, p₂, ..., p_n. As the New Year is coming, he wants to make his permutation as pretty as possible.

Permutation a₁, a₂, ..., a_n is prettier than permutation b₁, b₂, ..., b_n, if and only if there exists an integer k (1 ≤ k ≤ n) where a₁ = b₁, a₂ = b₂, ..., 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.

Input

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₁, p₂, ..., 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.

Output

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

Sample Input

Input

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

Output

1 2 4 3 6 7 5

Input

5 4 2 1 5 3 00100 00011 10010 01101 01010

Output

1 2 3 4 5

思路： 用floyd先将左右潜在的可以连通的边在邻接矩阵中标记出来，然后像冒泡一样的给他们排序一下就可以了 要注意两点： 一是刚开始开数组的时候，要从0开始开，不然用scanf输入会很麻烦 二是floyd的三层for循环，注意k的顺序要在最前面 这题也是对并查集数据结构的一种很好的理解，不过忽略了并查集分组的性质，而只关注了并查集的连通性 即通过邻接矩阵得到扩展边与边的连通关系

---

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int n;int p[307];char f[307][307];int main(){    while(~scanf("%d",&n))    {        for(int i = 0;i < n;i++)            scanf("%d",&p[i]);        for(int i = 0;i < n;i++)         {            scanf("%s",f[i]);            for(int j = 0;j < n;j++)                if(f[i][j] == '1')                    f[i][j] = '1';        }        for(int k = 0;k < n;k++)             for(int i = 0;i < n;i++)                for(int j = 0;j < n;j++)                    if(f[i][k]=='1' && f[k][j]=='1')                        f[i][j] = '1';                        for(int i = 0;i < n;i++)            for(int j = i+1;j < n;j++)                if(f[i][j]=='1' && p[j] < p[i])                    swap(p[i],p[j]);                for(int i = 0;i < n-1;i++)            printf("%d ",p[i]);        printf("%d\n",p[n-1]);    }    return 0;}