Не зважений орієнтований граф заданий своєю матрицею суміжності.

Потрібно побудувати його транзитивне замикання, тобто матрицю, в якій в \(i\) рядку і \(j\) стовпці знаходиться 1, якщо від вершини \(i\) можна добратися до вершини \(j\), або 0 в іншому випадку.

Вхідні дані

У першому рядку дано число \(𝑁\) (\(1≤𝑁≤100\)) – число вершин у графі.

Далі задана матриця суміжності графа: в \(N\) рядках задано по \(N\) чисел 0 або 1 в кожному.

\(𝑖\)-е число в \(𝑖\)-му рядку завжди дорівнює 1.

Вихідні дані

Необхідно вивести матрицю транзитивного замикання графа у форматі, аналогічним формату матриці суміжності.

Приклад вхідних даних

4
1 1 0 0
0 1 1 0
1 0 1 0
0 0 1 1

Приклад вихідних даних

1 1 1 0 
1 1 1 0 
1 1 1 0 
1 1 1 1