User ainta has a permutation *p*<sub class="lower-index">1</sub>, *p*<sub class="lower-index">2</sub>, ..., *p*<sub class="lower-index">*n*</sub>. As the New Year is coming, he wants to make his permutation as pretty as possible.

Permutation *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> is prettier than permutation *b*<sub class="lower-index">1</sub>, *b*<sub class="lower-index">2</sub>, ..., *b*<sub class="lower-index">*n*</sub>, if and only if there exists an integer *k* (1 ≤ *k* ≤ *n*) where *a*<sub class="lower-index">1</sub> = *b*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub> = *b*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*k* - 1</sub> = *b*<sub class="lower-index">*k* - 1</sub> and *a*<sub class="lower-index">*k*</sub> &lt; *b*<sub class="lower-index">*k*</sub> 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*<sub class="lower-index">*i*</sub> and *p*<sub class="lower-index">*j*</sub> (1 ≤ *i*, *j* ≤ *n*, *i* ≠ *j*) if and only if *A*<sub class="lower-index">*i*, *j*</sub> = 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*<sub class="lower-index">1</sub>, *p*<sub class="lower-index">2</sub>, ..., *p*<sub class="lower-index">*n*</sub> — 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*<sub class="lower-index">*i*, *j*</sub> 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* &lt; *j* ≤ *n*, *A*<sub class="lower-index">*i*, *j*</sub> = *A*<sub class="lower-index">*j*, *i*</sub> holds. Also, for all integers *i* where 1 ≤ *i* ≤ *n*, *A*<sub class="lower-index">*i*, *i*</sub> = 0 holds.
from typing import List

def prettiest_permutation(n :int, arr: List[int], s: List[str]) -> List[int]:
    par=[0]*310
    rank=[0]*310
    def init_union_find(V):#initial state
        for i in range(V):
            par[i]=i
            rank[i]=0
    def find(x):#where the root
        if par[x]==x:
            return x
        else:
            par[x]=find(par[x])
            return par[x]
    def unite(x,y):#x and y unite
        x=find(x)
        y=find(y)
        if x==y:
            return
        if rank[x]<rank[y]:
            par[x]=y
        else:
            par[y]=x
            if(rank[x] == rank[y]): rank[x] += 1
   
    init_union_find(310)
    edge=[0]*310
    node=[0]*310

    uv=[]
    for i in range(n):
        for j in range(n):
            if s[i][j]=='1':
                uv.append([i,j])
    for u,v in uv:
        unite(u,v)

    for i in range(len(arr)):
        for j in range(i+1,len(arr)):
            if arr[i]>arr[j] and find(i)==find(j):
                arr[i], arr[j]=arr[j], arr[i]
    return arr

n=int(input())
p=list(map(int, input().split()))
arr = []
for i in range(n):
    s=str(input())
    arr.append(s)
ans = prettiest_permutation(n, p, arr)
print (" ".join(map(str,ans)))
