Вам дано неорієнтований граф на вершинах. Для кожної пари вершин (i\neq j), визначте, чи існує Гамільтонів шлях, що починається в , а закінчується в .
Нагадаємо, що Гамільтонів шлях — це шлях, що складається з n-1 ребер, що проходить по всім вершинам рівно по одному разу.
Перший рядок містить одне ціле число (2 \le n \le 24) — кількість вершин в графі.
-ий з наступних рядків містить бінарний рядок s_i довжини . Його -ий символ завжди рівний 0, а для j\neq i його -ий символ рівний , якщо між вершинами та є ребро, і 0, якщо немає.
Гарантується, що для довільних i\neq j -ий символ -го рядка співпадає з -им символом -го рядка.
Виведіть рядків. В -му з них виведіть бінарний рядок довжини . Його -ий символ має бути рівним 0, а -ий при j\neq i має бути рівним 1, якщо між вершинами та є Гамільтонів шлях, і 0, якщо немає.
Example 1
Example 2
Example 3
В першому прикладі, Гамільтонів шлях є між парами та .
В другому прикладі, граф це цикл довжини . Гамільтонів шлях тут є лише між парами сусідніх вершин.
В третьому прикладі ми маємо повний граф на вершинах. Гамільтонів шлях тут є між кожною парою вершин.