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.
import queue
n = int(input())
perm = list(map(int, input().split()))
adj_table = []
for i in range(n):
    adj_table = adj_table + [list(map(lambda x:ord(x)-ord('0'),list(input())))]
q = queue.Queue()
marked = [False]*n
q.put(0)
marked[0] = True
subsets = []
where_indices = [-1]*n
pointer = -1
for i in range(n):
    if marked[i]:
        continue
    else:
        subsets = subsets + [[]]
        pointer = pointer + 1
        q.put(i)
        marked[i] = True
        while not q.empty():
            current_pos = q.get()
            where_indices[current_pos] = pointer
            subsets[pointer] = subsets[pointer] + [current_pos]
            for j in range(n):
                if adj_table[current_pos][j]==1 and not marked[j]:
                    q.put(j)
                    marked[j] = 1

for i in range(pointer + 1):
    for j in range(len(subsets[i])):
        subsets[i][j] = perm[subsets[i][j]]
    subsets[i] = sorted(subsets[i])


for i in range(n):
    print(subsets[where_indices[i]][0], end = " ")
    subsets[where_indices[i]] = subsets[where_indices[i]][1:]
