\includegraphics{https://static.e-olymp.com/content/a9/a91a6884c2324ed21ea0e8466fb4f3202cebac2e.jpg} Космічні мандрівники знайшли інформацію про шляхи між зоряними воротами. Використовуючи їх можно попасти в інші світи через космічні гіпертунелі. Шляхи між зорями, які існують у різних світах, задано матрицею. Всі ворота мають номери (\textbf{1} ≤ \textbf{i} ≤ \textbf{100}). Матриця шляхів містить \textbf{1} (одиницю) в позиції (\textbf{i},\textbf{j}), якщо існує прямий шлях від зірки (\textbf{i}) до зірки (\textbf{j}). Всі інші позиції містять \textbf{0} (нуль). Існування прямого шляху від зірки (\textbf{i}) до зірки (\textbf{j}) не гарантує існування такого ж шляху від (\textbf{j}) до (\textbf{i}). Але завжди є \textbf{1} в позиціях (\textbf{i},\textbf{i}). Задача полягає в настпуному. За заданою матрицею шляхів ви повинні знайти матрицю продвинутих шляхів, яка показує всі можливі шляхи. Ця матриця повинна давати інформацію про досягненість зірки (\textbf{k}) від кожної іншої зірки (\textbf{i}). Тобто, якщо існують шляхи від зірки (\textbf{i}) до зірки (\textbf{j}) і від зірки (\textbf{j}) до зірки (\textbf{k}), то існує також шлях і від (\textbf{i}) до (\textbf{k}). Існування шляху також представляеться числом \textbf{1} у відповідній позиції матриці. Так що продвинутий шлях може бути не обовязково прямим, але і містити проміжні зоряні ворота. \InputFile У першому рядку задано розмір матриці \textbf{M} (\textbf{M} ≤ \textbf{100}), наступні рядки - рядки матриці. Елементи в рядках відокремлюються одним пропуском. Вхідні дані коректні. \OutputFile Виведення - це матриця продвинутих шляхів, записана по рядках, елементи відокремлюються одним пропуском.