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.

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

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*$.