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.