Weapon of mass destruction

Your new weapon consist of K blocks each having a certain weight. However the blocks are randomly arranged in a straight line so you are not happy with the CentreOfMass of the weapon.

CentreOfMass of the weapon is defined as (W1 * 1 + W2 * 2 + W3 * 3 + … + WK * K)/K, where Wi is the weight of ith block. The blocks are magical so they require magical spells to redistribute them. A magical spell helps you to swap the position of two blocks.

Oh! you have forgotten some of the magical spells and thus your power is limited to swapping blocks at certain indices only.

You want to achieve the maximum value of CentreOfMass of your weapon by using the spells as many times you like.

Input Format

First line of the Input contains K, the number of blocks.

Next line contains K space separated integers, where ith integer is the weight of the ith block. All weights are distinct and has value between 1 and K ( inclusive ). 1 <= K <= 100.

Then follow K strings each of length K. If jth character of ith row is Y, it means you remember the spell to swap the blocks at ith and jth position.

Output Format

Print in a single line K space separated integers, describing the final configuration of blocks that give the maximum value of CentreOfMass of the weapon.

Sample Input

3

3 1 2

NNY

NNN

YNN

Sample Output

2 1 3

Explanation

According to the swapping matrix, you are only allowed to swap at the 1st and 3rd indices. You can exchange the first block with the last block to get the arrangement 2 1 3 from 3 1 2. Earlier the CentreOfMass was (31+12+23)/3 = 11/3 and the new one is (21+12+33)/3 = 13/3.