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: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Sorting

Greedy algorithms

Mathematics

Spanning trees
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
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]))


from sys import stdin
input = stdin.readline
from collections import defaultdict

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		group_members = defaultdict(list)
		for member in range(self.n):
			group_members[self.find(member)].append(member)
		return group_members
n = int(input())
p = list(map(int, input().split()))
a = [list(input().rstrip()) for i in range(n)]
uf = UnionFind(n)
for i in range(n):
	for j in range(n):
		if a[i][j] == '1':
			uf.union(i, j)
ans = [-1] * n
for r in uf.roots():
	m = uf.members(r)
	idx = []
	z = []
	for mm in m:
		idx.append(mm)
		z.append(p[mm])
	idx.sort()
	z.sort()
	for j in range(len(z)):
		ans[idx[j]] = z[j]
print(*ans)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class SMT:

	def __init__(self, arr):
		self.n = len(arr) - 1
		self.arr = [0] * (self.n << 2)
		self.lazy = [0] * (self.n << 2)

		def Build(l, r, rt):
			if l == r:
				self.arr[rt] = arr[l]
				return
			m = l + r >> 1
			Build(l, m, rt << 1)
			Build(m + 1, r, rt << 1 | 1)
			self.pushup(rt)
		Build(1, self.n, 1)

	def pushup(self, rt):
		self.arr[rt] = self.arr[rt << 1] + self.arr[rt << 1 | 1]

	def pushdown(self, rt, ln, rn):
		if self.lazy[rt]:
			self.lazy[rt << 1] += self.lazy[rt]
			self.lazy[rt << 1 | 1] = self.lazy[rt]
			self.arr[rt << 1] += self.lazy[rt] * ln
			self.arr[rt << 1 | 1] += self.lazy[rt] * rn
			self.lazy[rt] = 0

	def update(self, L, R, c, l=1, r=None, rt=1):
		if r == None:
			r = self.n
		if L <= l and r <= R:
			self.arr[rt] += c * (r - l + 1)
			self.lazy[rt] += c
			return
		m = l + r >> 1
		self.pushdown(rt, m - l + 1, r - m)
		if L <= m:
			self.update(L, R, c, l, m, rt << 1)
		if R > m:
			self.update(L, R, c, m + 1, r, rt << 1 | 1)
		self.pushup(rt)

	def query(self, L, R, l=1, r=None, rt=1):
		if r == None:
			r = self.n
		if L <= l and R >= r:
			return self.arr[rt]
		m = l + r >> 1
		self.pushdown(rt, m - l + 1, r - m)
		ans = 0
		if L <= m:
			ans += self.query(L, R, l, m, rt << 1)
		if R > m:
			ans += self.query(L, R, m + 1, r, rt << 1 | 1)
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

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

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [(ch, len(list(g))) for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None
t = 1
for i in range(t):
	n = N()
	p = RLL()
	a = []
	ans = []
	uf = UFS(n)
	for i in range(n):
		a.append(input())
	for i in range(n):
		for j in range(i):
			if a[i][j] == '1':
				uf.union(i, j)
	res = [[] for i in range(n)]
	for i in range(n):
		res[uf.find(i)].append(p[i])
	for i in range(n):
		res[i] = deque(sorted(res[i]))
	for i in range(n):
		ans.append(res[uf.find(i)].popleft())
	print(*ans)


from bisect import *
from sys import stdin, stdout

def dfs(i, j):
	global visited
	visited[i] = j
	for i1 in range(n):
		if matrix[i][i1] == '1' and (not visited[i1]):
			dfs(i1, j)
n = int(input())
arr = list(map(int, input().split()))
matrix = []
for i in range(n):
	matrix.append(list(input()))
visited = [0] * n
count = 1
for i in range(n):
	if not visited[i]:
		dfs(i, count)
		count += 1
for i in range(n):
	for j in range(i + 1, n):
		if visited[i] == visited[j]:
			if arr[i] > arr[j]:
				(arr[i], arr[j]) = (arr[j], arr[i])
print(*arr)


class NewYearPermutation:

	def __init__(self, num, m, s):
		self.n = num
		self.m = m
		self.s = s
		self.fa = [i for i in range(num)]

	def findest(self, x):
		if x == self.fa[x]:
			return x
		self.fa[x] = self.findest(self.fa[x])
		return self.fa[x]

	def solve(self):
		for i in range(self.n):
			for j in range(self.n):
				if self.s[i][j] == '1':
					u = self.findest(i)
					v = self.findest(j)
					if u != v:
						self.fa[u] = v
		temp = [[] for row in range(self.n)]
		for i in range(self.n):
			u = self.findest(i)
			temp[u].append(i)
		for i in range(self.n):
			for j in range(len(temp[i])):
				for k in range(j + 1, len(temp[i])):
					if self.m[temp[i][k]] < self.m[temp[i][j]]:
						(self.m[temp[i][k]], self.m[temp[i][j]]) = (self.m[temp[i][j]], self.m[temp[i][k]])
		self.printAns()

	def printAns(self):
		for i in range(len(self.m)):
			print(self.m[i], end=' ' if i < len(self.m) - 1 else '')
n = int(input())
p = list(map(int, input().split()))
s = [str()] * n
for i in range(n):
	s[i] = input()
NYP = NewYearPermutation(n, p, s)
NYP.solve()


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import time
start_time = time.time()
import collections as col
import math, string
from functools import reduce

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def bfs(graph, visited, node, queue, nodes):
	visited.add(node)
	nodes.remove(node)
	queue.append(node)
	queue = col.deque(queue)
	while queue:
		s = queue.popleft()
		for neighbour in graph[s]:
			if neighbour not in visited:
				visited.add(neighbour)
				nodes.remove(neighbour)
				queue.append(neighbour)
	return (visited, nodes)

def solve():
	N = getInt()
	A = getInts()
	graph = col.defaultdict(set)
	for n in range(N):
		S = getStr()
		for i in range(n + 1, N):
			if S[i] == '1':
				graph[i].add(n)
				graph[n].add(i)
	nodes = set([j for j in range(N)])
	connected_components = []
	while nodes:
		node = next(iter(nodes))
		(visited, nodes) = bfs(graph, set(), node, [], nodes)
		connected_components.append(visited)
	ans = [0] * N
	while connected_components:
		arr = list(connected_components.pop())
		arr.sort(reverse=True)
		tmp = []
		for i in arr:
			tmp.append(A[i])
		tmp.sort(reverse=True)
		while tmp:
			(idx, el) = (arr.pop(), tmp.pop())
			A[idx] = el
	print(*A)
	return
solve()


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

def dfs(i, k):
	global visited
	visited[i] = k
	for j in range(n):
		if not visited[j] and b[i][j] == 1:
			dfs(j, k)
visited = [0] * n
k = 1
for i in range(n):
	if not visited[i]:
		dfs(i, k)
		k += 1
for i in range(n):
	for j in range(i + 1, n):
		if visited[i] == visited[j]:
			if a[i] > a[j]:
				(a[i], a[j]) = (a[j], a[i])
print(*a)


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


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


from collections import defaultdict
graph = defaultdict(list)
n = int(input())
arr = list(map(int, input().split()))
mat = []
for i in range(n):
	mat.append(list(map(int, input())))
for i in range(n):
	for j in range(n):
		if i != j and mat[i][j] == 1:
			graph[i].append(j)
ans = []
visited = [False for i in range(n)]
for i in range(n):
	if visited[i] == False:
		q = [i]
		visited[i] = True
		t = []
		while q != []:
			u = q[0]
			q.pop(0)
			t.append(arr[u])
			for v in graph[u]:
				if visited[v] == False:
					visited[v] = True
					q.append(v)
		t.sort()
		ans.append(t)
pointers = [0 for i in range(len(ans))]
final = []
for i in arr:
	for j in range(len(ans)):
		if i in ans[j]:
			final.append(ans[j][pointers[j]])
			pointers[j] += 1
print(*final)


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
Neo = lambda : list(map(int, input().split()))

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

def Union(a, b):
	a = find(a)
	b = find(b)
	if rank[a] < rank[b]:
		(a, b) = (b, a)
	par[b] = a
	rank[a] += rank[b]
(n,) = Neo()
l = Neo()
par = list(range(n))
rank = [0] * n
for i in range(n):
	s = input()
	for j in range(n):
		if s[j] == '1':
			Union(i, j)
s = set()
for i in range(n):
	s.add(find(i))
dic = defaultdict(list)
for i in range(n):
	j = find(i)
	dic[j].append(l[i])
for i in s:
	dic[i].sort()
	dic[i].reverse()
ans = []
for i in range(n):
	j = find(i)
	ans.append(dic[j].pop())
print(*ans)


Z = input
n = int(Z())
q = [*map(int, Z().split())]

def path(r):
	while p[r] >= 0:
		r = p[r]
	return r
k = {}
p = {}
r = 0
for i in range(n):
	s = Z().strip()
	for j in range(i + 1):
		if j < i and s[j] == '0':
			continue
		(a, b) = (i, j)
		if a in k:
			if b in k:
				(va, vb) = (path(k[a]), path(k[b]))
				if va > vb:
					p[va] = vb
				elif va < vb:
					p[vb] = va
			else:
				k[b] = k[a]
		elif b in k:
			k[a] = k[b]
		else:
			k[a] = r
			k[b] = r
			p[r] = -1
			r += 1
v = [[] for _ in [0] * r]
o = [''] * n
for i in range(n):
	v[path(k[i])].append(q[i])
for i in range(r):
	v[i] = sorted(v[i], reverse=1)
for i in range(n):
	o[i] = str(v[path(k[i])].pop())
print(' '.join(o))


def dfs(p):
	q = [p]
	vis[p] = 1
	(a, b) = ([p], [g[p][1]])
	while q:
		v = q.pop()
		for i in g[v][0]:
			if not vis[i]:
				vis[i] = 1
				q.append(i)
				a.append(i)
				b.append(g[i][1])
	return (a, b)
n = int(input())
(*a,) = map(int, input().split())
g = {a[i]: [set(), i] for i in range(n)}
for i in range(n):
	(*b,) = [int(i) for i in input()]
	for j in range(n):
		if b[j]:
			g[a[i]][0].add(a[j])
vis = [0] * (n + 1)
for i in range(1, n + 1):
	if not vis[i]:
		(x, y) = dfs(i)
		x.sort()
		y.sort()
		for j in range(len(x)):
			a[y[j]] = x[j]
print(*a)


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] = 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)))


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

def dfs(u):
	global 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():
	global 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
		global 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)))
main()


n = int(input())
a = list(map(int, input().split()))
mt = [[] for _ in range(n)]
for i in range(n):
	mt[i] = list(input())
p = [i for i in range(n)]
sz = [1 for i in range(n)]

def find(i):
	if i != p[i]:
		p[i] = find(p[i])
	return p[i]

def union(i, j):
	i = find(i)
	j = find(j)
	if i == j:
		return
	if sz[i] > sz[j]:
		sz[i] += sz[j]
		p[j] = i
	else:
		sz[j] += sz[i]
		p[i] = j
for i in range(n):
	for j in range(n):
		if mt[i][j] == '1':
			union(i, j)
l = [[] for _ in range(n)]
r = [[] for _ in range(n)]
for i in range(n):
	l[find(i)].append(i)
	r[find(i)].append(a[i])
b = [0 for _ in range(n)]
for i in range(len(l)):
	l[i] = sorted(l[i])
	r[i] = sorted(r[i])
	for j in range(len(l[i])):
		b[l[i][j]] = r[i][j]
print(*b)


n = int(input())
s = list(map(int, input().split()))
inds = {}
ids = {}
id = 0
for i in s:
	inds[id] = [id]
	ids[id] = id
	id += 1

def unite(a, b):
	if ids[a] == ids[b]:
		return
	idb = ids[b]
	gb = inds.pop(idb)
	inds[ids[a]] += gb
	for i in gb:
		ids[i] = ids[a]
for i in range(n):
	a = list(map(int, input()))
	for j in range(n):
		if a[j]:
			unite(i, j)
ans = [-1] * n
for i in inds:
	ff = []
	inds[i].sort()
	for j in inds[i]:
		ff += (s[j],)
	ff.sort()
	for j in range(len(ff)):
		ans[inds[i][j]] = ff[j]
print(*ans)


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


import sys, os
from io import BytesIO, IOBase
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
n = iinp()
arr = lmp()
matrix = [list(inp()) for i in range(n)]
for i in range(n):
	for j in range(n):
		if matrix[i][j] == '1':
			for k in range(n):
				if matrix[j][k] == '1':
					matrix[i][k] = '1'
					matrix[k][i] = '1'
				elif matrix[i][k] == '1':
					matrix[j][k] = '1'
					matrix[k][j] = '1'
for i in range(1, n + 1):
	ind = arr.index(i)
	for j in range(ind):
		if arr[j] > i and matrix[j][ind] == '1':
			(arr[ind], arr[j]) = (arr[j], arr[ind])
			break
print(*arr)


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]))


from sys import stdout
from sys import stdin

def get():
	return stdin.readline().strip()

def getf():
	return [int(i) for i in get().split()]

def put(a, end='\n'):
	stdout.write(str(a) + end)

def putf(a, sep=' ', end='\n'):
	stdout.write(sep.join(map(str, a)) + end)

def bfs(g, i, v):
	q = [i]
	usd = set()
	while q:
		t = q.pop()
		usd.add(t)
		for j in g[t]:
			v[j] = False
			if j not in usd:
				q.append(j)
	return usd
from collections import defaultdict as dd

def main():
	n = int(get())
	p = getf()
	a = [[int(i) for i in get()] for j in range(n)]
	g = dd(list)
	for i in range(n - 1):
		for j in range(i + 1, n):
			if a[i][j]:
				g[i] += [j]
				g[j] += [i]
	dsu = [0] * n
	v = [True] * n
	x = 1
	for i in range(n):
		if v[i] == True:
			for j in bfs(g, i, v):
				dsu[j] = x
			x += 1
	for i in range(n - 1):
		for j in range(i + 1, n):
			if p[i] > p[j]:
				if dsu[i] == dsu[j]:
					(p[i], p[j]) = (p[j], p[i])
	putf(p)
main()


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 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()


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
adj = defaultdict(list)
for i in range(n):
	line = [int(i) for i in input().strip()]
	for j in range(n):
		if line[j]:
			adj[a[i]].append(a[j])
v = [0] * (n + 1)
cmps = []
for i in range(n):
	if not v[a[i]]:
		cmp = []
		q = [a[i]]
		while q:
			e = q.pop()
			if not v[e]:
				cmp.append(e)
				v[e] = 1
			for j in adj[e]:
				if not v[j]:
					q.append(j)
		cmps.append(sorted(cmp))
labels = [0] * n
ct = 0
for i in range(len(cmps)):
	for j in range(n):
		if a[j] in cmps[i]:
			labels[j] = ct
	ct += 1
ans = [0] * n
for i in range(ct):
	q = sorted(cmps[i], reverse=True)
	for j in range(n):
		if labels[j] == i:
			ans[j] = q[-1]
			q.pop()
print(*ans)


import sys
(mod, MOD) = (1000000007, 998244353)
from collections import deque, Counter, OrderedDict, defaultdict

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()

def dfs(curr):
	stack = [curr]
	component = [curr]
	visited[curr] = True
	while stack:
		x = stack.pop()
		for child in mydict[x]:
			if not visited[child]:
				component.append(child)
				visited[child] = True
				stack.append(child)
	return component
n = int(input())
Arr = get_array()
mydict = defaultdict(list)
index = dict()
for i in range(n):
	index[i] = Arr[i]
for i in range(n):
	string = input()
	for j in range(n):
		if string[j] == '1':
			mydict[i].append(j)
visited = [False] * (n + 1)
components = []
for i in enumerate(Arr):
	if not visited[i[0]]:
		component = dfs(i[0])
		components.append(component)
copy = []
copy_cat = []
for i in range(len(components)):
	x = []
	y = []
	for j in range(len(components[i])):
		value = (index[components[i][j]], components[i][j])
		value2 = (components[i][j], index[components[i][j]])
		x.append(value)
		y.append(value2)
		components[i][j] = value
	copy.append(x)
	copy_cat.append(y)
for i in copy:
	i.sort()
for i in copy_cat:
	i.sort()
for i in range(len(components)):
	for j in range(len(components[i])):
		Arr[copy_cat[i][j][0]] = copy[i][j][0]
print(*Arr)


import os
import sys
from io import BytesIO, IOBase
from collections import deque
from collections import defaultdict

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	d = []
	for _ in range(n):
		d.append(list(map(int, input())))
	graph = [set() for _ in range(n)]
	for i in range(n):
		for j in range(n):
			if i != j and d[i][j]:
				graph[i].add(j)
	for i in range(n):
		graph[i] = list(graph[i])
	vis = [0] * n
	for i in range(n):
		if vis[i]:
			continue
		stack = [i]
		vis[i] = 1
		temp = [arr[i]]
		j = 0
		while j != len(stack):
			z = stack[j]
			for item in graph[z]:
				if vis[item] == 0:
					vis[item] = 1
					stack.append(item)
					temp.append(arr[item])
			j += 1
		stack.sort()
		temp.sort()
		for k in range(len(stack)):
			arr[stack[k]] = temp[k]
	print(*arr)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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


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 sys
n = int(input())
a = list(map(lambda x: int(x), sys.stdin.readline().split()))
matrix = []
for _ in range(n):
	row = input()
	row = list(row)
	row = list(map(lambda x: int(x), row))
	matrix.append(row)

class DisjSet:

	def __init__(self, n):
		self.rank = [1] * n
		self.parent = [i for i in range(n)]
		self.extra = []

	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):
		xset = self.find(x)
		yset = self.find(y)
		if xset == yset:
			self.extra.append((x, y))
			return
		if self.rank[xset] < self.rank[yset]:
			self.parent[xset] = yset
		elif self.rank[xset] > self.rank[yset]:
			self.parent[yset] = xset
		else:
			self.parent[yset] = xset
			self.rank[xset] = self.rank[xset] + 1
obj = DisjSet(n)
for i in range(n):
	for j in range(n):
		if matrix[i][j] == 1:
			obj.Union(i, j)
hashmap = {}
for i in range(n):
	temp = obj.find(i)
	if temp not in hashmap:
		hashmap[temp] = []
	hashmap[temp].append(i)
final = [0 for _ in range(n)]
for k in hashmap:
	temp = [a[i] for i in hashmap[k]]
	temp.sort()
	for i in range(0, len(temp)):
		final[hashmap[k][i]] = temp[i]
print(*final)


I = lambda : 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):
	global 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))


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))
n = int(input())
p = list(map(int, input().split()))
matrix = [input() for _ in range(n)]
print(solve(n, p, matrix))


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 999999999999999999999999
alphabets = 'abcdefghijklmnopqrstuvwxyz'

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class SegTree:

	def __init__(self, n):
		self.N = 1 << n.bit_length()
		self.tree = [0] * (self.N << 1)

	def update(self, i, j, v):
		i += self.N
		j += self.N
		while i <= j:
			if i % 2 == 1:
				self.tree[i] += v
			if j % 2 == 0:
				self.tree[j] += v
			(i, j) = (i + 1 >> 1, j - 1 >> 1)

	def query(self, i):
		v = 0
		i += self.N
		while i > 0:
			v += self.tree[i]
			i >>= 1
		return v

def SieveOfEratosthenes(limit):
	isPrime = [True] * (limit + 1)
	isPrime[0] = isPrime[1] = False
	primes = []
	for i in range(2, limit + 1):
		if not isPrime[i]:
			continue
		primes += [i]
		for j in range(i * i, limit + 1, i):
			isPrime[j] = False
	return primes

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		n = ri()
		a = ria()
		matrix = []
		for i in range(n):
			matrix.append(list(rs()))
		swap = {}
		graph = [[] for i in range(n)]
		vis = [0] * n
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == '1':
					if (i, j) in swap or (j, i) in swap:
						continue
					else:
						(x, y) = (min(i, j), max(i, j))
						swap[x, y] = 1
						graph[x].append(y)
						graph[y].append(x)
		col = [0] * n

		def dfs(v, c):
			vis[v] = 1
			for u in graph[v]:
				if not vis[u]:
					dfs(u, c)
			col[v] = c
		c = 0
		for i in range(n):
			if not vis[i]:
				dfs(i, c)
				c += 1
		for colour in range(c):
			pos = []
			num = []
			for p in range(n):
				if col[p] == colour:
					pos.append(p)
					num.append(a[p])
			num = sorted(num)
			for i in range(len(pos)):
				a[pos[i]] = num[i]
		wia(a)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


def dfs(i, visited, a, m, n):
	l = [i]
	visited[i] = True
	for j in range(n):
		if m[i][j] == 1 and (not visited[j]):
			l.append(j)
			x = dfs(j, visited, a, m, n)
			l.extend(x)
	return l

def main():
	n = int(input())
	a = list(map(int, input().split()))
	m = [list(map(int, list(input()))) for i in range(n)]
	visited = [False] * n
	for i in range(n):
		if not visited[i]:
			x = dfs(i, visited, a, m, n)
			val = [a[i] for i in x]
			val.sort()
			x.sort()
			for j in range(len(x)):
				a[x[j]] = val[j]
	print(' '.join(list(map(str, a))))
main()


from __future__ import print_function
import sys
from collections import *
from heapq import *
from functools import *
import re
from itertools import *
INF = float('inf')
NINF = float('-inf')
try:
	input = raw_input
except:
	pass

def read_string():
	return input()

def read_string_line():
	return [x for x in input().split(' ')]

def read_int_line():
	return [int(x) for x in input().split(' ')]

def read_int():
	return int(input())
n = read_int()
arr = read_int_line()
grid = []
for _ in range(n):
	grid.append(read_string())
p = [-1] * n

def find(x):
	if p[x] == -1:
		return x
	p[x] = find(p[x])
	return p[x]

def union(x, y):
	x = find(x)
	y = find(y)
	if x == y:
		return
	p[x] = y
for y in range(n):
	for x in range(n):
		if grid[y][x] == '1':
			union(x, y)
d = defaultdict(list)
for x in range(n):
	d[find(x)].append(x)
for v in d.values():
	l = [arr[i] for i in v]
	l.sort()
	v.sort()
	for (i, a) in zip(v, l):
		arr[i] = a
print(' '.join((str(x) for x in arr)))


import math as mt
import sys, string
input = sys.stdin.readline
from collections import defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())

def dfs(n, k, vis):
	vis[n] = k
	for i in a[n]:
		if vis[i] == 0:
			dfs(i, k, vis)
n = I()
l = L()
adj = []
a = []
for i in range(n):
	a.append([])
for i in range(n):
	s = input().strip()
	for j in range(n):
		if s[j] == '1':
			a[i].append(j)
vis = [0] * n
k = 1
for i in range(n):
	if vis[i] == 0:
		dfs(i, k, vis)
		k += 1
for i in range(1, k):
	ind = []
	val = []
	for j in range(n):
		if vis[j] == i:
			ind.append(j)
			val.append(l[j])
	if len(val) > 0:
		val.sort()
		h = 0
		for j in ind:
			l[j] = val[h]
			h += 1
print(*l)


n = int(input())
arr = [0] + list(map(int, input().split()))
ans = [0 for i in range(n + 1)]
m = []
for _ in range(n):
	m.append(list(input()))
parents = [i for i in range(n + 1)]
ranks = [1 for i in range(n + 1)]

def find(x):
	if parents[x] != x:
		parents[x] = find(parents[x])
	return parents[x]

def union(x, y):
	xs = find(x)
	ys = find(y)
	if xs == ys:
		return
	if ranks[xs] > ranks[ys]:
		parents[ys] = xs
	elif ranks[ys] > ranks[xs]:
		parents[xs] = ys
	else:
		parents[ys] = xs
		ranks[xs] += 1
for i in range(n):
	for j in range(n):
		if m[i][j] == '1':
			union(i + 1, j + 1)
ps = {}
for i in range(1, n + 1):
	p = find(i)
	if p in ps:
		ps[p].append(i)
	else:
		ps[p] = [i]
for parent in ps:
	temp = []
	for element in ps[parent]:
		temp.append(arr[element])
	temp.sort()
	for i in range(len(temp)):
		ans[ps[parent][i]] = temp[i]
print(*ans[1:])


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


n = int(input())
l = list(map(int, input().split()))
from collections import defaultdict
d1 = defaultdict(list)
d2 = defaultdict(list)
adj = []
for i in range(n + 1):
	adj.append([])
v = [0] * (n + 1)
for i in range(n):
	s = input()
	for j in range(n):
		if s[j] == '1':
			adj[i + 1].append(j + 1)
			adj[j + 1].append(i + 1)

def dfs(x, c):
	v[x] = 1
	d1[c].append(x - 1)
	d2[c].append(l[x - 1])
	for i in adj[x]:
		if not v[i]:
			dfs(i, c)
c = 1
ans = [0] * n
for i in range(1, n + 1):
	if not v[i]:
		dfs(i, c)
		c += 1
for i in d1:
	d1[i].sort()
	d2[i].sort()
	for j in range(len(d1[i])):
		ans[d1[i][j]] = d2[i][j]
print(*ans)


def dfs(node, g):
	global 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)


def dfs(node):
	component.append(node)
	visited[node] = True
	for (adj, edge) in enumerate(graph[node]):
		if edge == '1' and (not visited[adj]):
			dfs(adj)
n = int(input())
permutation = list(map(int, input().split()))
graph = [input() for _ in range(n)]
visited = [False] * n
components = []
result = [None] * n
for i in range(n):
	if not visited[i]:
		component = []
		dfs(i)
		components.append(component)
for i in range(len(components)):
	components[i].sort()
	numbers = sorted([permutation[j] for j in components[i]])
	for j in range(len(numbers)):
		result[components[i][j]] = numbers[j]
print(' '.join(map(str, result)))


from queue import PriorityQueue

def getVals(type=str):
	return list(map(type, input().split()))
n = int(input())
L = getVals(int)
par = [i for i in range(n)]

def findPar(idx):
	if par[idx] != idx:
		par[idx] = findPar(par[idx])
	return par[idx]

def isSameSet(x, y):
	return findPar(x) == findPar(y)

def solve(L):
	for i in range(n):
		L[i] -= 1
	adjMatrix = [None for i in range(n)]
	for i in range(n):
		adjMatrix[i] = list(input())
		adjMatrix[i] = list(map(lambda x: int(1000000000.0) if x == '0' else 1, adjMatrix[i]))
		adjMatrix[i][i] = 1
	for i in range(n):
		for j in range(n):
			if adjMatrix[i][j] == 1:
				if not isSameSet(i, j):
					par[findPar(i)] = findPar(j)
	for i in range(n):
		for j in range(i + 1, n):
			if isSameSet(i, j):
				if L[j] < L[i]:
					(L[i], L[j]) = (L[j], L[i])
	L = list(map(lambda x: x + 1, L))
	return L
print(*solve(L))


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)


n = int(input())
raw = [int(i) for i in input().split()]
g = [[False for i in range(n)] for j in range(n)]
for i in range(n):
	current = input()
	for j in range(n):
		g[i][j] = current[j] == '1'
ok = [[False for i in range(n)] for j in range(n)]

def dfs(v, g, o):
	global ok
	ok[o][v] = True
	for i in range(n):
		if g[v][i] and (not ok[o][i]):
			dfs(i, g, o)
res = [raw[i] for i in range(n)]
for i in range(n):
	dfs(i, g, i)
	for j in range(i, n):
		if ok[i][j] and res[j] < res[i]:
			temp = res[i]
			res[i] = res[j]
			res[j] = temp
res_str = str(res[0])
for i in range(1, n):
	res_str += ' ' + str(res[i])
print(res_str)


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


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
int1 = lambda x: int(x) - 1

def input():
	return sys.stdin.readline().rstrip('\r\n')
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])

def solve():
	G = defaultdict(list)

	def addEdge(a, b):
		G[a].append(b)

	def dfs(node):
		d = deque()
		d.append(node)
		vis[node] = True
		ind = []
		t = []
		while d:
			x = d.pop()
			ind.append(x)
			t.append(A[x])
			for i in G.get(x, []):
				if not vis[i]:
					vis[i] = True
					d.append(i)
		ind.sort(reverse=True)
		t.sort(reverse=True)
		while t:
			Ans[ind.pop()] = t.pop()
	(n,) = aj()
	A = aj()
	vis = [False] * (n + 1)
	for i in range(n):
		s = input()
		for j in range(len(s)):
			if s[j] == '1':
				addEdge(i, j)
	Ans = [-1] * n
	for i in range(n):
		if not vis[i]:
			dfs(i)
	print(*Ans)
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
solve()


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)


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
n = int(input())
l = list(map(int, input().split()))
graph = {i: set() for i in range(n)}
for i in range(n):
	s = input()
	for j in range(n):
		if s[j] == '1' and i != j:
			graph[i].add(j)
			graph[j].add(i)
visited = set()
for i in range(n):
	if i not in visited:
		a = []
		b = []
		stack = [i]
		while stack:
			x = stack.pop()
			if x not in visited:
				b.append(x)
				a.append(l[x])
				for j in graph[x]:
					stack.append(j)
					if x in graph[j]:
						graph[j].remove(x)
				visited.add(x)
		a.sort()
		b.sort()
		for i in range(len(a)):
			l[b[i]] = a[i]
print(*l)


import logging
import sys
from asyncio.log import logger
from _operator import pos
nivel_log = logging.ERROR
nivel_log = logging.DEBUG
logger_cagada = None

class DisjointSet:

	def __init__(self, n):
		self.count = n
		self.parent = list(range(n))
		self.rank = [0] * n
		self.es_raiz = set(list(range(n)))
		self.llaves = [set([x]) for x in range(n)]

	def find(self, p):
		self.validate(p)
		if p != self.parent[p]:
			self.parent[p] = self.find(self.parent[p])
		return self.parent[p]

	def connected(self, p, q):
		return self.find(p) == self.find(q)

	def union(self, p, q):
		rootP = self.find(p)
		rootQ = self.find(q)
		if rootP == rootQ:
			return
		if self.rank[rootP] < self.rank[rootQ]:
			self.parent[rootP] = rootQ
			self.es_raiz.remove(rootP)
			self.llaves[rootQ] |= self.llaves[rootP]
		else:
			if self.rank[rootP] > self.rank[rootQ]:
				self.parent[rootQ] = rootP
			else:
				self.parent[rootQ] = rootP
				self.rank[rootP] += 1
			self.es_raiz.remove(rootQ)
			self.llaves[rootP] |= self.llaves[rootQ]
		self.count -= 1

	def validate(self, p):
		n = len(self.parent)
		if p < 0 or p >= n:
			raise IndexError('index {} is not between 0 and {}'.format(p, n - 1))

	def raices(self):
		return list(self.es_raiz)

	def llaves_en_conjuntos_disjuntos(self):
		return [self.llaves[x] for x in self.raices()]

def perputa_ano_nuevo_core(nodos_tam, llaves, ariscas):
	caca = DisjointSet(nodos_tam)
	for arisca in ariscas:
		if caca.connected(arisca[0], arisca[1]):
			continue
		caca.union(arisca[0], arisca[1])
	for monton in caca.llaves_en_conjuntos_disjuntos():
		nums_en_posiciones = []
		for pos_act in monton:
			nums_en_posiciones.append(llaves[pos_act])
		nums_en_posiciones.sort()
		idx_num = 0
		for pos_act in sorted(monton):
			llaves[pos_act] = nums_en_posiciones[idx_num]
			idx_num += 1
	return llaves

def caca_comun_lee_linea_como_num():
	return int(sys.stdin.readline().strip())

def caca_comun_lee_linea_como_monton_de_numeros():
	return list(map(int, sys.stdin.readline().strip().split(' ')))

def perputa_ano_nuevo_main():
	nodos_tam = caca_comun_lee_linea_como_num()
	llaves = caca_comun_lee_linea_como_monton_de_numeros()
	ariscas = []
	for i in range(nodos_tam):
		miedas = sys.stdin.readline().strip()
		for j in range(nodos_tam):
			if miedas[j] == '1':
				ariscas.append((i, j))
		if not i:
			pass
	fuck = perputa_ano_nuevo_core(nodos_tam, llaves, ariscas)
	print('{}'.format(' '.join(map(str, fuck))))
FORMAT = '[%(filename)s:%(lineno)s - %(funcName)20s() ] %(message)s'
logging.basicConfig(level=nivel_log, format=FORMAT)
logger_cagada = logging.getLogger('asa')
logger_cagada.setLevel(nivel_log)
perputa_ano_nuevo_main()


n = int(input())
dsu = [i for i in range(n)]
a = list(map(int, input().split()))
b = ['' for _ in range(n)]
for i in range(n):
	b[i] = input()

def get(a):
	if dsu[a] == a:
		return a
	dsu[a] = get(dsu[a])
	return dsu[a]

def uni(a, b):
	a = get(a)
	b = get(b)
	if a + b & 4:
		(a, b) = (b, a)
	dsu[a] = b
for i in range(n - 1):
	for j in range(i + 1, n):
		if b[i][j] == '1':
			uni(i, j)
c = [[] for i in range(n)]
for i in range(n):
	x = get(i)
	c[x].append(i)
d = [0] * n
for i in range(n):
	d[a[i] - 1] = i
for i in range(n):
	a[c[dsu[d[i]]].pop(0)] = i + 1
print(*a)


from sys import stdin
input = stdin.readline

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

def union(i, j):
	(i, j) = (find(i), find(j))
	if i == j:
		return
	if rank[i] > rank[j]:
		(i, j) = (j, i)
	elif rank[i] == rank[j]:
		rank[j] += 1
	p[i] = j
n = int(input())
l = list(map(int, input().split()))
p = list(range(n))
rank = [0] * n
for i in range(n):
	s = input()
	for j in range(n):
		if s[j] == '1':
			union(i, j)
s = set()
for i in range(n):
	s.add(find(i))
dic = {i: [] for i in s}
for i in range(n):
	j = find(i)
	dic[j].append(l[i])
for i in s:
	dic[i].sort()
	dic[i].reverse()
ans = []
for i in range(n):
	j = find(i)
	ans.append(dic[j].pop())
print(*ans)


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)

class DSU(object):

	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):
	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())
p = list(map(int, input().split()))
a = [list(map(int, list(input()))) for _ in range(n)]
v = [0] * n
l = n + 1
xx = [-1] * n

def dfs(x):
	global l
	v[x] = 1
	if xx[x] == -1:
		l = min(x, l)
	for i in range(n):
		if a[x][i] == 1 and v[i] == 0:
			dfs(i)
x = [0] * (n + 1)
for i in range(n):
	x[p[i]] = i
for i in range(1, n + 1):
	v = [0] * n
	l = n + 1
	dfs(x[i])
	xx[l] = i
print(' '.join(map(str, xx)))


n = int(input())
val = list(map(int, input().split(' ')))
adj_lis = [[] for i in range(n)]
matrix = []
for i in range(n):
	matrix.append(input())
for x in range(n):
	for y in range(n):
		if matrix[x][y] == '1':
			adj_lis[x].append(y)

def bfs(start, adj_lis, visited, n):
	visited[start] = True
	queue = [start]
	newly_visited = [False for i in range(n)]
	newly_visited[start] = True
	while queue != []:
		v = queue[0]
		for neig in adj_lis[v]:
			if not visited[neig]:
				newly_visited[neig] = True
				visited[neig] = True
				queue.append(neig)
		del queue[0]
	return newly_visited
components = []
visited = [False for i in range(n)]
for i in range(n):
	if not visited[i]:
		res = bfs(i, adj_lis, visited, n)
		new_comp = []
		for j in range(len(res)):
			if res[j]:
				new_comp.append(j)
		components.append(new_comp)
for comp in components:
	c_vals = [val[x] for x in comp]
	c_vals = sorted(c_vals)
	for x in range(len(comp)):
		val[comp[x]] = c_vals[x]
for x in val:
	print(x, end=' ')


def recursive_dfs(graph, start, path=[]):
	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]))