Obeleži sve kategorije koje odgovaraju problemu

Дата је квадратна матрица $A$ димензије $N$, која представља директне авионске везе између $N$ градова. Елемент $a_{i,j}$ је једнак један ако постоји директан лет из града $i$ за град $j$, а нула иначе.

Одредити и исписати матрицу исте димензије, која приказује везе између истих градова уз највише једно преседање. Сматрати да је сваки град у директној вези са самим собом, без обзира на улазне вредности.

Улаз

У првом реду стандардног улаза налази се број $N$, број градова ($1 \leq N \leq 10$). У наредних $N$ редова налази се низ од $N$ нула или јединица. Јединица у реду $i$ на месту $j$ значи да постоји директан лет од града $i$ до града $j$, а нула да не постоји.

Излаз

На стандардни излаз исписати $N$ редова, у сваком по једну врсту резултујуће матрице. Елемент на позицији $(i, j)$ резултујуће матрице једнак је 1 ако постоји директна веза, или веза са једним преседањем између одговарајућих градова, а 0 иначе.

Пример

Улаз

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

Излаз

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

Објашњење

Из првог у трећи град се стиже преко четвртог града.

Из другог у четврти град се стиже преко првог града.

Из трећег у четврти град се стиже преко првог града.

Из четвртог у први град се стиже преко трећег града.

Из четвртог у други град се стиже преко трећег града.