A permutation is a list of K numbers, each between 1 and K (both inclusive), that has no duplicate elements.

Permutation X is lexicographically smaller than Permutation Y if for some \(i \le K\):

All of the first i-1 elements of X are equal to first i-1 elements of Y.
ith element of X is smaller than ith element of Y.

You are given a permutation P, you can exchange some of its elements as many times as you want in any order. You have to find the lexicographically smallest Permutation that you can obtain from P.

K is less than \(101\).

Input Format:
First line of input contains K being the size of permutation.
Next line contains K single spaced numbers indicating the permutation.
Each of next K lines contains K characters, character j of line i is equal to 'Y' if you can exchange \(i\;th\) and \(j\;th\) element of a permutation, and 'N' otherwise.

Output Format:
Print K numbers with a space separating each of them indicating the permutation.