Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. New Year Permutation

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputUser ainta has a permutation *p*_{1}, *p*_{2}, ..., *p*_{n}. As the New Year is coming, he wants to make his permutation as pretty as possible.

Permutation *a*_{1}, *a*_{2}, ..., *a*_{n} is prettier than permutation *b*_{1}, *b*_{2}, ..., *b*_{n}, if and only if there exists an integer *k* (1 ≤ *k* ≤ *n*) where *a*_{1} = *b*_{1}, *a*_{2} = *b*_{2}, ..., *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 if *A*_{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*_{1}, *p*_{2}, ..., *p*_{n} — the permutation *p* that user ainta has. Each integer between 1 and *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 the *i*-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* where 1 ≤ *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

5

4 2 1 5 3

00100

00011

10010

01101

01010

Output

1 2 3 4 5

Note

In the first sample, the swap needed to obtain the prettiest permutation is: (*p*_{1}, *p*_{7}).

In the second sample, the swaps needed to obtain the prettiest permutation is (*p*_{1}, *p*_{3}), (*p*_{4}, *p*_{5}), (*p*_{3}, *p*_{4}).

A permutation *p* is a sequence of integers *p*_{1}, *p*_{2}, ..., *p*_{n}, consisting of *n* distinct positive integers, each of them doesn't exceed *n*. The *i*-th element of the permutation *p* is denoted as *p*_{i}. The size of the permutation *p* is denoted as *n*.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/25/2021 23:04:53 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|