【Good Bye 2014B】【Floyd or 并查集】New Year Permutation 全排列有位置交换序列使得字典序尽可能小

本文主要是介绍【Good Bye 2014B】【Floyd or 并查集】New Year Permutation 全排列有位置交换序列使得字典序尽可能小，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

User ainta has a permutation p₁, p₂, ..., p_n. As the New Year is coming, he wants to make his permutation as pretty as possible.

Permutation a₁, a₂, ..., a_n is prettier than permutation b₁, b₂, ..., b_n, if and only if there exists an integer k (1 ≤ k ≤ n) wherea₁ = b₁, a₂ = b₂, ..., 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 ifA_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₁, p₂, ..., p_n — the permutation p that user ainta has. Each integer between 1and 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 thei-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 where1 ≤ 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.

Examples

input

7
5 2 4 3 6 7 1
0001001
0000000
0000010
1000001
0000000
0010000
1001000

output

1 2 4 3 6 7 5

input

output

1 2 3 4 5

Note

In the first sample, the swap needed to obtain the prettiest permutation is: (p₁, p₇).

In the second sample, the swaps needed to obtain the prettiest permutation is (p₁, p₃), (p₄, p₅), (p₃, p₄).

$\text{[math]}$

A permutation p is a sequence of integers p₁, p₂, ..., p_n, consisting of n distinct positive integers, each of them doesn't exceed n. Thei-th element of the permutation p is denoted as p_i. The size of the permutation p is denoted as n.

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 303, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int a[N], p[N];
char s[N][N];
int n;
bool use[N];
int ans[N];
int main()
{while (~scanf("%d", &n)){for (int i = 1; i <= n; ++i){scanf("%d", &a[i]);p[a[i]] = i;}for (int i = 1; i <= n; ++i){scanf("%s", s[i] + 1);s[i][i] = '1';}for (int k = 1; k <= n; ++k){for (int i = 1; i <= n; ++i){for (int j = 1; j <= n; ++j){if (s[i][k] == '1'&&s[k][j] == '1')s[i][j] = '1';}}}MS(use, 0);for (int i = 1; i <= n; ++i){for (int j = 1; j <= n; ++j)if(!use[j]&&s[i][p[j]]=='1'){ans[i] = j;use[j] = 1;p[j] = i;p[a[i]] = p[j];break;}}for (int i = 1; i <= n; ++i)printf("%d ", ans[i]);puts("");}return 0;
}
/*
【题意】
给你一个长度为n（300）的全排列。
同时给你一个n*n的01矩阵s[][]
我们可以交换两个数，当且仅当它们所在的的下标i,j对应着的s[i][j]为1。
问你我们可以得到的最小字典序的排列【类型】
floyd【分析】
这题可以用floyd做。
我们对矩阵做闭包传递的floyd。(或者——并查集)
那么，任意两个位置的数是否可以交换我们就知道了。这个类似于冒泡排序的过程，只要有一个交换链存在，任意一个数都可以位移到它想要的位置。
于是这种做法是可行的。就可以AC啦。【时间复杂度&&优化】
O(n^3)【数据】*/

这篇关于【Good Bye 2014B】【Floyd or 并查集】New Year Permutation 全排列有位置交换序列使得字典序尽可能小的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！