Algorithms and Data Structures

Minimize the Sequence

Given a sequence of n numbers , you are asked to minimize it. A sequence can be lexicographically minimized by swapping two allowed elements of the sequence. You are allowed to swap elements as many times as possible. Yet, there are certain indices that can be swapped and certain ones that cannot be swapped with each other.
Lexicographic comparison of two sequences
A sequence is lexicographically smaller than the sequence if and only if there exists an integer k (1 ≤ k ≤ n) where , , …, and . In other words, there exists an index k where , while all the other numbers before k are equal.
Given the matrix of allowed swaps, you are asked to find out the lexicographically smallest sequence possible to obtain from the initial sequence.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 300).
The next line contains n space-separated integers (1 ≤ ≤ n) representing the initial sequence, where all the numbers are different.
The next n lines contain n 0s and 1s representing if the swap between two indices is allowed. If the value at row i and column j is 1, it means that the swap between the i-th and j-th elements is allowed. If the value is 0, then the swap isn’t allowed.

Output

The program should print the lexicographically smallest possible sequence possible to obtain from the given one.

Examples

Input
Output
5 4 2 1 5 3 00100 00011 10010 01101 01010
1 2 3 4 5
7 5 2 4 3 6 7 1 0001001 0000000 0000010 1000001 0000000 0010000 1001000
1 2 4 3 6 7 5

Explanation

  1. We can perform the following swaps:
    1. ↔  ⇒ 1 2 4 5 3
    2. ↔  ⇒ 1 2 4 3 5
    3. ↔  ⇒ 1 2 3 4 5
  1. We can just swap and ⇒ 1 2 4 3 6 7 5
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue