CF500B.New Year Permutation

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.

用户 ainta 有一个排列 $p_1, p_2, ..., p_n$。随着新年临近，他希望将该排列变得尽可能“漂亮”。

排列 $a_1, a_2, ..., a_n$ 比排列 $b_1, b_2, ..., b_n$ 更漂亮，当且仅当存在一个整数 $k$（$1 ≤ k ≤ n$），使得 $a_1 = b_1,\, a_2 = b_2,\, ..., \, a_{k-1} = b_{k-1}$，且 $a_k < b_k$ 同时成立。

众所周知，排列 $p$ 非常敏感，只能通过交换其中两个不同元素来修改。但交换操作比你想象的更困难。给定一个 $n × n$ 的 0-1 矩阵 $A$，用户 ainta 当且仅当 $A_{i,j} = 1$ 时，才允许交换 $p_i$ 和 $p_j$（其中 $1 ≤ i,\,j ≤ n$，且 $i ≠ j$）。

给定排列 $p$ 和矩阵 $A$，用户 ainta 想知道他所能得到的最漂亮的排列。

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.

第一行包含一个整数 $n$（$1 \leq n \leq 300$）——表示排列 $p$ 的大小。

第二行包含 $n$ 个以空格分隔的整数 $p_1,\ p_2,\ \dots,\ p_n$——即用户 ainta 所拥有的排列 $p$。给定排列中，$1$ 到 $n$ 之间的每个整数恰好出现一次。

接下来的 $n$ 行描述矩阵 $A$。第 $i$ 行包含 $n$ 个字符，每个字符为 '0' 或 '1'，表示矩阵 $A$ 的第 $i$ 行。第 $i$ 行的第 $j$ 个字符 $A_{i,j}$ 表示矩阵 $A$ 中第 $i$ 行与第 $j$ 列交点处的元素。保证对所有满足 $1 \leq i < j \leq n$ 的整数 $i,j$，均有 $A_{i,j} = A_{j,i}$ 成立；且对所有满足 $1 \leq i \leq n$ 的整数 $i$，均有 $A_{i,i} = 0$ 成立。

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

在第一行且唯一的一行中，输出 n 个用空格分隔的整数，描述所能得到的最漂亮的排列。

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

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.

在第一个样例中，为得到最漂亮的排列所需执行的交换操作是：$(p_1,\,p_7)$。

在第二个样例中，为得到最漂亮的排列所需执行的交换操作是：$(p_1,\,p_3),\,(p_4,\,p_5),\,(p_3,\,p_4)$。

一个排列 $p$ 是由 $n$ 个互不相同的正整数组成的序列 $p_1,\,p_2,\,\dots,\,p_n$，且每个数均不超过 $n$。排列 $p$ 的第 $i$ 个元素记作 $p_i$。排列 $p$ 的大小记作 $n$。