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.


-----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_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.


-----Output-----

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


-----Examples-----
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



-----Note-----

In the first sample, the swap needed to obtain the prettiest permutation is: (p_1, p_7).

In the second sample, the swaps needed to obtain the prettiest permutation is (p_1, p_3), (p_4, p_5), (p_3, p_4).  [Image] 

A permutation p is a sequence of integers p_1, p_2, ..., p_{n}, consisting of n distinct positive integers, each of them doesn't exceed n. The i-th element of the permutation p is denoted as p_{i}. The size of the permutation p is denoted as n.

Difficulty: interview

Starter code:

Solutions:
"""
Codeforces Contest Good Bye 2014 Contest Problem B

Author  : chaotic_iak
Language: Python 3.4.2
"""

################################################### SOLUTION

def main():
    n, = read()
    p = read()
    dsu = DSU()
    for i in range(n):
        a = read(0)
        dsu.make()
        for j in range(i):
            if a[j] == "1":
                dsu.union(j, i)
    used = [0] * n
    res = [0] * n
    for i in range(n):
        if not used[i]:
            pr = dsu.find(i)
            indices = []
            elements = []
            for j in range(n):
                if dsu.find(j) == pr:
                    used[j] = 1
                    indices.append(j)
                    elements.append(p[j])
            elements.sort()
            for i,e in zip(indices, elements):
                res[i] = e
    write(res)

#################################################### HELPERS

class DSU(object):
    """
    Implements disjoint-set data structure as disjoint-set forest, with {0,1,...,n-1} as elements.

    Methods:
    make(): add a new element and returns its index
    find(x): return representative of x
    union(x, y): merge the sets containing x and y

    Not to be used publicly:
    _parent: a list of ints for the parent of each vertex, used internally; call find instead
    _rank: a list of ints for the rank of trees, ensuring trees are binary and hence O(lg n) worst case
    __init__(): called when initialization, initialize DSU to be empty
    __str__(): return a readable string description of the DSU; meant to be printed while debugging
    """

    def __init__(self):
        self._parent = []
        self._rank = []

    def make(self):
        i = len(self._parent)
        self._parent.append(i)
        self._rank.append(0)
        return i

    def find(self, x):
        if self._parent[x] != x:
            self._parent[x] = self.find(self._parent[x])
        return self._parent[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        if xr == yr: return
        if self._rank[xr] < self._rank[yr]:
            self._parent[xr] = yr
        elif self._rank[yr] < self._rank[xr]:
            self._parent[yr] = xr
        else:
            self._parent[yr] = xr
            self._rank[xr] += 1

    def __str__(self):
        s = "DSU\n"
        for i in range(len(self._parent)):
            s += str(i) + " in set " + str(self.find(i)) + " with rank " + str(self._rank[self.find(i)]) + "\n"
        return s

def read(mode=2):
    # 0: String
    # 1: List of strings
    # 2: List of integers
    inputs = input().strip()
    if mode == 0: return inputs
    if mode == 1: return inputs.split()
    if mode == 2: return list(map(int, inputs.split()))

def write(s="\n"):
    if s is None: s = ""
    if isinstance(s, list): s = " ".join(map(str, s))
    s = str(s)
    print(s, end="")

write(main())

n = int(input())
l = list(map(int,input().split()))
best = l
swaps = []
for i in range(n):
    p = list(input())
    for j in range(n):
        if j>i and p[j] == '1':
            swaps.append([i,j])

group = []
for i in range(n):
    group.append([i])
    
for i in range(len(swaps)):
    x = swaps[i][1]
    y = swaps[i][0]
    while isinstance(group[x],int) == 1:
        x = group[x]
    while isinstance(group[y],int) == 1:
        y = group[y]
    if y != x:
        group[y] += group[x]
        group[x] = y

for i in range(n):
    if isinstance(group[i],list) == 1:
        group[i] = sorted(group[i])

for i in range(n):
    if isinstance(group[i],list) == 1:
        x = []
        for j in range(len(group[i])):
            x.append(l[group[i][j]])
        x = list(sorted(x))
        for j in range(len(group[i])):
            l[group[i][j]] = x[j]

s = str(l[0])
for i in range(1,n):
    s += ' '+str(l[i])
print(s)


def dfs(node, g) :
    nonlocal visited, M, N
    for i in range(N) :
        if M[node][i] == '0' or visited[i] : continue
        visited[i] = True
        g.append(i)
        dfs(i, g)
    
N = int(input())
P = list(map(int, input().split(' ')))
M = [input() for i in range(N)]

G = []
visited = [False]*N
for i in range(N) :
    if visited[i] : continue
    visited[i] = True
    g = [i]
    dfs(i, g)
    g.sort()
    G.append(g)

for g in G :
    for i in range(len(g)) :
        for j in range(i+1, len(g)) :
            if P[g[i]] > P[g[j]] : P[g[i]], P[g[j]] = P[g[j]], P[g[i]]

ans = ""
for i in range(len(P)) :
    ans += str(P[i]) + ' '
ans = ans[:-1]
print(ans)
    


n = int(input())
p = list(map(int, input().split()))
a = [list(map(int, list(input()))) for _ in range(n)]

groups = []

for i in range(n):
    s = set()
    s.add(i)
    for j in range(n):
        if a[i][j] == 1:
            s.add(j)
    if len(s) > 1:
        groups.append(s)

i = 0
while i < len(groups):
    j = i + 1
    while j < len(groups):
        if len(groups[i] & groups[j]) == 0:
            j += 1
            continue
        groups[i] |= groups[j]
        groups.pop(j)
        j = i + 1
    i += 1

groups = [sorted(list(s)) for s in groups]

for g in groups:
    i = len(g)
    while i > 0:
        j = 0
        while j < i - 1:
            if p[g[j]] > p[g[j+1]]:
                p[g[j]], p[g[j+1]] = p[g[j+1]], p[g[j]]
            j += 1
        i -= 1

print(' '.join(map(str, p)))


#!/usr/bin/env python3

n = int(input())
p = [int(x) for x in input().split()]
a = [[int(c) for c in input()] for _ in range(n)]

exchange = []
for i in range(n):
    s = set()
    s.add(i)
    for j in range(n):
        if a[i][j] == 1:
            s.add(j)
    if len(s) > 1:
        exchange.append(s)


i = 0
while i < len(exchange) - 1:
    j = i + 1
    while j < len(exchange):
        if exchange[i] & exchange[j]:
            exchange[i] |= exchange[j]
            exchange.pop(j)
            j = i + 1
        else:
            j += 1
    i += 1
exchange = [sorted(s) for s in exchange]


for ex in exchange:
    for i in range(len(ex) - 1):
        for j in range(i + 1, len(ex)):
            if p[ex[i]] > p[ex[j]]:
                p[ex[i]], p[ex[j]] = p[ex[j]], p[ex[i]]


print(" ".join(map(str, p)))


def dfs(v):
    pos.append(v)
    used[v] = True
    for g in range(n):
        if int(s[v][g]) and not used[g]:
            dfs(g)

n = int(input())
p = list(map(int, input().split()))
s = [input() for i in range(n)]
used = [False] * n
for j in range(n):
    if not used[j]:
        pos = []
        dfs(j)
        values = [p[i] for i in pos]
        pos.sort()
        values.sort()
        for (i, po) in enumerate(pos):
            p[po] = values[i]
print(' '.join([str(x) for x in p]))

def dfs(i, visited, g):
	indexes = []
	visited.add(i)
	for j in g[i]:
		if j not in visited:
			indexes.extend(dfs(j, visited, g))
	indexes.append(i)
	return indexes

def solve(n, p, g):
	visited = set()
	result = [0] * n
	for i in range(n):
		if i not in visited:
			indexes = dfs(i, visited, g)
			values = [p[i] for i in indexes]

			indexes = sorted(indexes)
			values = sorted(values)

			for j in range(len(indexes)):
				result[indexes[j]] = values[j]
	return result




def main():
	n = int(input())
	p = list(map(int, input().split()))
	swaps = []
	for i in range(n):
		row = input()
		temp = []
		for j in range(n):
			if row[j] == '1':
				temp.append(j)
		swaps.append(temp)
	result = solve(n, p, swaps)
	print(" ".join(map(str, result)))


def __starting_point():
	main()
__starting_point()

def dfs(v):
    pos.append(v)
    used[v] = True
    for g in range(n):
        if int(s[v][g]) and not used[g]:
            dfs(g)

n = int(input())
p = list(map(int, input().split()))
s = [input() for i in range(n)]
used = [False] * n
for j in range(n): 
    if not used[j]:
        pos = []
        dfs(j)
        values = [p[i] for i in pos]
        pos.sort()
        values.sort()
        for (i, po) in enumerate(pos):
            p[po] = values[i]
print(' '.join([str(x) for x in p]))

I=lambda:list(map(int,input().split()))
n = int(input())
permutation = list(I())
components = [-1] * n
matrix = [[int(c) for c in input()] for _ in range(n)]

current = 0
def dfs(i):
	nonlocal current
	if components[i] < 0:
		components[i] = current
		for j, b in enumerate(matrix[i]):
			if(b):
				dfs(j)

for i in range(n):
	dfs(i)
	current += 1

slots = [components[i] for i in range(n)]

groups = []
for i in range(current):
	groups.append(sorted([permutation[j] for j in range(n) if components[j] == i]))

pretty = []
for p in slots:
	pretty.append(str(groups[p][0]))
	groups[p] = groups[p][1:]
print(' '.join(pretty))


I = lambda:list(map(int,input().split()))
n = int(input()); permutation = list(I())

row = lambda: [int(c) for c in input()]
matrix = [row() for _ in range(n)]
components = [-1] * n

def dfs(i):
	nonlocal current
	if components[i] < 0:
		components[i] = current
		row = enumerate(matrix[i])
		row = [j for j, a in row if a > 0]
		for x in row: dfs(x)

current = 0
for i in range(n):
	dfs(i)
	current += 1

groups = []
for i in range(current):
	indices = [j for j, c in enumerate(components) if c == i]
	groups.append(sorted([permutation[j] for j in indices]))

pretty = []
for p in components:
	pretty.append(str(groups[p][0]))
	groups[p] = groups[p][1:]
print(' '.join(pretty))


from queue import Queue as Q

def fill(start, used, a):
	q = Q()
	q.put(start)
	n = len(a)
	used[start] = start + 1
	while not q.empty():
		next = q.get()
		for i in range(n):
			if a[next][i] == '0' or used[i]:
				continue
			used[i] = start + 1
			q.put(i)

n = int(input())
p = [int(x) for x in input().split()]
a = []
for i in range(n):
	a.append(input())
used = [0] * n
lists = [[] for i in range(n)]
for i in range(n):
	if not used[i]:
		fill(i, used, a)
	lists[used[i] - 1].append(p[i])
for l in lists:
	l.sort()
for i in range(n):
	p[i] = lists[used[i] - 1][0]
	lists[used[i] - 1].pop(0)
print(' '.join(str(x) for x in p))


def main():
    def dfs(t):
        pos.append(t)
        unused[t] = False
        for k, (a, u) in enumerate(zip(A[t], unused)):
            if a and u:
                dfs(k)

    n = int(input())
    pp = list(map(int, input().split()))
    A = [list(map(int, input())) for _ in range(n)]
    unused = [True] * n
    for i, f in enumerate(unused):
        if f:
            pos = []
            dfs(i)
            for j, v in zip(sorted(pos), sorted(pp[_] for _ in pos)):
                pp[j] = v
    print(' '.join(map(str, pp)))


def __starting_point():
    main()
__starting_point()

def dfs(i):
	ret = []
	if not used[i]:
		used[i] = True
		ret += [i]
	for j in range(n): 
		if a[i][j]==1 and not used[j]:
			ret.extend(dfs(j))
	return ret



n = int(input())
p = list(map(int,input().split()))
ans = p
a = [list(map(int,input())) for i in range(n)]
used = [False for i in range(n)]
for i in range(n):
	if not used[i]:
		temp = []
		idx = dfs(i)
		idx.sort()
		for j in idx:
			temp.append(p[j])
		temp.sort()
		for k,j in enumerate(idx):
			ans[j] = temp[k]

print(" ".join(list(map(str,p))))


def recursive_dfs(graph, start, path=[]):
  '''recursive depth first search from start'''
  path=path+[start]
  for node in graph[start]:
    if not node in path:
      path=recursive_dfs(graph, node, path)
  return path

x = []
sa = int(input())
toed = list(map(int, input().split(' ')))
for i in range(sa):
    x.append(input())

graph = {}
for i in range(sa):
    graph[i] = []

marked = [False] * sa

for bad in range(sa):
    for asdf in range(bad+1, sa):
        if x[bad][asdf] == '1':
            graph[bad].append(asdf)
            graph[asdf].append(bad)

done = []
for i in range(sa):
  if not marked[i]:
      a = recursive_dfs(graph, i)
      done.append(a)
      for j in recursive_dfs(graph, i):
          marked[j] = True

final = [0] * sa

for i in done:
    o = [toed[a] for a in i]
    o.sort()
    i.sort()
    for a in range(len(i)):
        final[i[a]] = o[a]

print(' '.join([str(i) for i in final]))



n = int(input())
p = [int(i) for i in input().split()]
s = ()
for i in range(n):
    s += (input(),)
z = [False] * n
x,y = [],[]
def dfs(i):
    if not z[i]:
        nonlocal x
        z[i] = True
        x.append(i)
        y.append(p[i])
        for j in range(n):
            if s[i][j] == '1': dfs(j)

for i in range(n):
    if not z[i]:
        x,y = [],[]
        dfs(i)
        x.sort()
        y.sort()
        for j in range(len(x)): p[x[j]] = y[j]

print(" ".join([str(i) for i in p]))



used = [0 for i in range(333)]
p = []
t = []
n = 0
c = []
d = []

def dfs(v):
    used[v] = 1
    c.append(v)
    d.append(p[v])
    for i in range(len(p)):
        if t[v][i] == '1' and not used[i]:
            dfs(i)
def main():
    nonlocal n
    nonlocal p
    nonlocal t
    nonlocal used
    nonlocal c
    nonlocal d
    n = int(input())
    p = [int(i) for i in input().split()]
    t = []
    ans = [0 for i in range(n)]
    for i in range(n):
        t.append(input())
    for i in range(n):
        if not used[i]:
            c = []
            d = []
            dfs(i)
            k = len(c)
            for num,val in zip(sorted(c), sorted(d)):
                ans[num] = val 
    for elem in ans:
        print(elem, end = ' ')
def __starting_point():
    main()
__starting_point()

def dfs(v):
    pos.append(v)
    used[v] = True
    for g in range(n):
        if int(s[v][g]) and not used[g]:
            dfs(g)

n = int(input())
p = list(map(int, input().split()))
s = [input() for i in range(n)]
used = [False] * n
for j in range(n):
    if not used[j]:
        pos = []
        dfs(j)
        values = [p[i] for i in pos]
        pos.sort()
        values.sort()
        for (i, po) in enumerate(pos):
            p[po] = values[i]
print(' '.join([str(x) for x in p]))

n = int(input())
p = list(map(int, input().split()))
g = [list() for i in range(n)]
for k in range(n):
    a = list(map(int, input()))
    for i in range(n):
        if a[i]: g[k].append(i)
def dfs(v):
    nonlocal c
    was[v] = True
    c[v] = color
    for u in g[v]:
        if not was[u]:
            dfs(u)
c = [0] * n
color = 1
for i in range(n):
    was = [False] * n
    if c[i] == 0:
        dfs(i)
        color += 1
b = [list() for i in range(n)]
for i in range(n):
    b[c[i] - 1].append(p[i])
for i in range(n):
    b[i].sort()
ans = [0] * n
cur = [0] * n
for i in range(n):
    x = c[i] - 1
    ans[i] = b[x][cur[x]]
    cur[x] += 1
print(*ans)


import bisect,sys
from collections import deque, namedtuple
sys.setrecursionlimit(20000)
N = 1050
par = [i for i in range(1050)]
siz = [1]*N

def find(i):
    if i == par[i]: return i
    par[i] = find(par[i])
    return par[i]

def merge(a,b):
    a = find(a)
    b = find(b)
    if siz[a] < siz[b]: a,b = b,a
    par[b] = a
    siz[a] += siz[b]

def main():
    n = int(input())
    l = [int(i) for i in input().split()]
    a = [ [ord(c)-ord('0') for c in input()] for j in range(n) ]
    for i in range(n):
        for j in range(n):
            if a[i][j]:
                merge(i,j)
    d = [[] for i in range(n)]
    for i in range(n):
        a = find(i)
        bisect.insort(d[a],l[i])

    for i in range(n):
        a = find(i)
        print(d[a][0],end=" ")
        d[a] = d[a][1:]

def __starting_point():
    main()
__starting_point()

import bisect,sys
from collections import deque, namedtuple
sys.setrecursionlimit(20000)
N = 1050
par = [i for i in range(1050)]
siz = [1]*N

def find(i):
    if i == par[i]: return i
    par[i] = find(par[i])
    return par[i]

def merge(a,b):
    a = find(a)
    b = find(b)
    if siz[a] < siz[b]: a,b = b,a
    par[b] = a
    siz[a] += siz[b]

def main():
    n = int(input())
    l = [int(i) for i in input().split()]
    a = [ [ord(c)-ord('0') for c in input()] for j in range(n) ]
    for i in range(n):
        for j in range(n):
            if a[i][j]:
                merge(i,j)
    d = [[] for i in range(n)]
    cnt = [0]*n
    for i in range(n):
        a = find(i)
        d[a].append(l[i])

    for i in range(n):
        d[i] = sorted(d[i])


    for i in range(n):
        a = find(i)
        print(d[a][cnt[a]],end=" ")
        cnt[a] += 1

def __starting_point():
    main()
__starting_point()

import bisect,sys
from collections import deque, namedtuple
sys.setrecursionlimit(20000)
N = 1050
par = [i for i in range(1050)]
siz = [1]*N

def find(i):
    if i == par[i]: return i
    par[i] = find(par[i])
    return par[i]

def merge(a,b):
    a = find(a)
    b = find(b)
    if siz[a] < siz[b]: a,b = b,a
    par[b] = a
    siz[a] += siz[b]

def main():
    n = int(input())
    l = [int(i) for i in input().split()]
    a = [ [ord(c)-ord('0') for c in input()] for j in range(n) ]
    for i in range(n):
        for j in range(n):
            if a[i][j]:
                merge(i,j)
    d = [[] for i in range(n)]
    cnt = [0]*n
    for i in range(n):
        a = find(i)
        d[a].append(l[i])

    for i in range(n):
        d[i] = sorted(d[i])


    for i in range(n):
        a = find(i)
        print(d[a][cnt[a]],end=" ")
        cnt[a] += 1

def __starting_point():
    main()
__starting_point()

def dfs(v):
    pos.append(v)
    used[v]=1
    for i in range(n):
        if s[v][i]=="1" and not used[i]:
            dfs(i)



n = int(input())
a = list(map(int,input().split()))
s = [input() for _ in range(n)]
used = [0]*n
for i in range(n):
    if not used[i]:
        pos = []
        dfs(i)
        values = [a[i] for i in pos]
        pos.sort()
        values.sort()
        for i,j in enumerate(pos):
            a[j] = values[i]

print(" ".join(str(x) for x in a))


"""
	Author		: Arif Ahmad
	Date  		: 
	Algo  		: 
	Difficulty	: 
"""

n 		= None
p 		= []
a 		= []
visited = []
ids 	= []
values	= []


def dfs(u):
	nonlocal visited, ids, values

	visited[u] = True
	for v in range(n):
		if (not visited[v]) and (a[u][v] == '1'):
			ids.append(v)
			values.append(p[v])
			dfs(v)


def main():
	nonlocal n, p, a, visited

	n = int(input())
	p = list((int(_) for _ in input().split()))
	a = [[0 for i in range(n)] for j in range(n)]
	for i in range(n):
		a[i] = input()

	visited = [False] * n
	for i in range(n):
		if visited[i]: continue
		nonlocal ids, values
		ids 	= [i]
		values 	= [p[i]]
		dfs(i)
		ids 	= sorted(ids)
		values 	= sorted(values) 
		for x, y in zip(ids, values):
			p[x] = y    

	print(" ".join(str(_) for _ in p))


def __starting_point():
    main()

__starting_point()

"""http://codeforces.com/problemset/problem/500/B"""

from collections import defaultdict

class DFS:
    visited = None
    graph = None

    def __init__(self, graph):
        self.visited = set()
        self.graph = graph

    def dfs(self, node):
        self.visited.add(node)
        for v in self.graph[node]:
            if v not in self.visited:
                self.dfs(v)

def solve(n, p, m):
    graph = defaultdict(list)
    for i in range(n):
        for j in range(n):
            if m[i][j] == '1':
                graph[i].append(j)
    for num in range(1, n+1):
        i = p.index(num)
        d = DFS(graph)
        d.dfs(i)
        for j in range(i):
            if j in d.visited and p[i] < p[j]:
                p[i], p[j] = p[j], p[i]
    return ' '.join(map(str, p))

def __starting_point():
    n = int(input())
    p = list(map(int, input().split()))
    matrix = [input() for _ in range(n)]
    print(solve(n, p, matrix))

__starting_point()

n = int(input())
t = list(map(int, input().split()))
a = [input() for i in range(n)]
u = [0] * n
def dfs(i):
    p.append(i)
    u[i] = 1
    for j in range(n):
        if a[i][j] == '1' and not u[j]:
            dfs(j)
for i in range(n):
    if not u[i]:
        p = []
        dfs(i)
        k = [t[i] for i in p]
        p.sort()
        k.sort()
        for i, j in enumerate(p):
            t[j] = k[i]
print(' '.join(map(str, t)))