Космические путешественники нашли информацию о путях между звездными вратами. Используя их можно попасть в другие миры через космические гипертуннели. Пути между звездами, которые существуют в разных мирах, представляются матрицей. Все ворота имеет имеют номера (1 ≤ i ≤ 100). Матрица путей содержит 1 (единицу) в позиции (i, j), если существует прямой путь от звезды (i) до звезды (j).

Все остальные позиции содержат 0 (нуль). Существование прямого пути от звезды (i) до звезды (j) не гарантирует существование такого же пути от (j) до (i). Но всегда есть 1 в позициях (i, i).

Задача заключается в следующем. По заданной матрице путей, вы должны найти матрицу продвинутых путей, которая показывает все возможные пути. Эта матрица должна давать информацию достижима ли звезда (k) от каждой другой звезды (i). То есть, если существуют пути от звезды (i) до звезды (j) и от звезды (j) до звезды (k), то существует так же путь и от (i) до (k). Существование пути также представляется числом 1 в соответствующей позиции матрицы.

Так что продвинутый путь может бы не только прямым, но и содержать промежуточные врата.

Входные данные

Первая строка содержит размер матрицы M (M ≤ 100), последующие строки - строки матрицы. Элементы в строках разделяются одним пробелом. Входные данные корректны.

Выходные данные

Вывод - это матрица продвинутых путей записанная построчно, элементы разделяются одним пробелом.