У пользователя ainta есть перестановка p1, p2, ..., pn. Приближается Новый год, и юноша хочет как можно лучше украсить свою перестановку.
Перестановка a1, a2, ..., an красивее перестановки b1, b2, ..., bn тогда и только тогда, когда существует целое число k (1 ≤ k ≤ n), для которого верно a1 = b1, a2 = b2, ..., ak - 1 = bk - 1 и ak < bk.
Как известно, перестановка p — очень чувствительная натура, так что её можно изменять только путем перестановки двух различных элементов. Но переставлять элементы сложнее, чем вы думаете. Вам дана матрица A размера n × n, такая что пользователь ainta может переставить значения pi и pj (1 ≤ i, j ≤ n, i ≠ j) тогда и только тогда, когда Ai, j = 1.
Дана перестановка p и матрица A. Пользователь ainta хочет знать, какая из достижимых перестановок самая красивая.
В первой строке записано целое число n (1 ≤ n ≤ 300) — размер перестановки p.
Во второй строке записано n целых чисел через пробел p1, p2, ..., pn — перестановка p, имеющаяся у пользователя ainta. Каждое целое число от 1 до n встречается ровно один раз в данной перестановке.
Следующие n строк описывают матрицу A. При этом, i-я из них содержит n символов '0' или '1' и описывает i-ю строку A. j-й символ i-ой строки Ai, j — это элемент, находящийся на пересечении i-й строки и j-го столбца A. Гарантируется, что для всех целых чисел i, j, для которых 1 ≤ i < j ≤ n, выполняется условие Ai, j = Aj, i. Также, для всех целых чисел i, для которых 1 ≤ i ≤ n, выполняется условие Ai, i = 0.
В первой и единственной строке выведите n целых чисел через пробел, описывающих самую красивую достижимую перестановку.
7
5 2 4 3 6 7 1
0001001
0000000
0000010
1000001
0000000
0010000
1001000
1 2 4 3 6 7 5
5
4 2 1 5 3
00100
00011
10010
01101
01010
1 2 3 4 5
В первом примере для достижения самой красивой перестановки необходимо переставить элементы (p1, p7).
Во втором примере для достижения самой красивой перестановки необходимо переставить (p1, p3), (p4, p5), (p3, p4).
Перестановка p — это последовательность целых чисел p1, p2, ..., pn, состоящая из n различных положительных целых чисел, каждое из которых не превышает n. i-й элемент перестановки p обозначается как pi. Размер перестановки p обозначается как n.
| Good Bye 2014 |
|---|
| Закончено |
