가중치가 없는 방향 그래프 \(G\)가 주어진다.

모든 정점 쌍 \((i,j)\)에 대하여 정점 \(i\)에서 정점 \(j\)로 가는 경로가 존재하는지 구하시오. 경로는 하나 이상의 간선으로 이루어진다.

입력

첫째 줄에 정점의 개수 \(N\)이 주어진다.

다음 \(N\)개의 줄에 그래프의 인접 행렬이 주어진다. \(i\)번째 줄의 \(j\)번째 수가 1이면 정점 \(i\)에서 정점 \(j\)로 가는 간선이 존재하고, 0이면 존재하지 않는다. 주어지는 인접 행렬의 대각선 성분은 항상 0이다.

출력

총 \(N\)개의 줄을 출력한다. \(i\)번째 줄의 \(j\)번째 수는 정점 \(i\)에서 정점 \(j\)로 가는 경로가 존재하면 1, 존재하지 않으면 0이어야 한다.

각 줄의 수는 공백으로 구분한다.

제한 사항

• \(1 \le N \le 100\)

예제 입력 1

3
0 1 0
0 0 1
1 0 0

예제 출력 1

1 1 1
1 1 1
1 1 1

예제 설명 1

세 정점이 하나의 순환 경로를 이룬다. 따라서 서로 다른 모든 정점으로 이동할 수 있으며, 각 정점에서 출발하여 다시 자기 자신으로 돌아오는 경로도 존재한다.

예제 입력 2

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

예제 출력 2

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

예제 설명 2

정점들이 \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\) 순서로 연결되어 있다. 예를 들어 \(1\)번 정점에서 \(3\)번 정점이나 \(4\)번 정점으로 가는 직접 간선은 없지만, 다른 정점을 거치면 도달할 수 있다.

어느 정점에서도 자기 자신으로 돌아오는 경로는 존재하지 않는다. 또한 \(4\)번 정점에서 다른 정점으로 가는 경로도 존재하지 않는다.