Задано орієнтовний зважений граф. За його матрицею суміжності потрібно для кожної пари вершин визначити, чи існує найкоротший шлях між ними чи ні.

Найкоротший шлях може не існувати з двох причин:

• Немає жодного шляху.
• Є шлях як завгодно маленької ваги.

Вхідні дані

У першому рядку задається кількість вершин графа n (1 ≤ n ≤ 100). У наступних n рядках записано по n чисел, які задають матрицю суміжності графа (j-те число у i-ому рядку відповідає вазі ребра з вершини i у вершину j). В ній число 0 означає відсутність ребра, а довільне інше число - наявність ребра відповідної ваги. Всі числа по модулю не перевищують 100.

Вихідні дані

Виведіть n рядків по n чисел: j-те число у i-ому рядку повинно бути рівним 0, якщо шлях з i у j не існує, 1 - якщо існує найкоротший шлях, і 2 - якщо існує шлях як завгодно маленької ваги.