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.
n = int(input())
p = [int(x) for x in input().split()]
adj = [[] for x in range(n+1)]
for x in range(1,n+1):
	temp = input()
	i=1
	while i<n:
		if temp[i-1]=='1':
			adj[x].append(i)
			adj[i].append(x)
		i+=1


ans = [0 for x in range(n)]
component_index = [-1 for _ in range(n + 1)]
def dfs(u, c):
	component_index[u] = c
	for v in adj[u]:
		if component_index[v] == -1:
			dfs(v, c)

num_components = 0
for u in range(1, n + 1):
	if component_index[u] == -1:
		dfs(u, num_components)
		num_components += 1

swappable = [[] for x in range(num_components)]
perms = [[] for x in range(num_components)]
i=0
while i<n+1:
	if component_index[i]!=-1:
		swappable[component_index[i]].append(i)
		perms[component_index[i]].append(p[i-1])
	i+=1

for x in perms:
	x = x.sort()
i=0
while i<num_components:
	j=0
	while j<len(swappable[i]):
		ans[swappable[i][j]-1] = perms[i][j]
		j+=1
	i+=1
print(*ans)