N개의 정점으로 이루어진 방향 그래프가 있다.

그래프의 정보는 인접 행렬 형태로 주어진다.

i번째 줄의 j번째 수는 i번 정점에서 j번 정점으로 가는 간선의 가중치를 의미한다.

단, 모든 간선의 가중치는 양수이다. 따라서 입력값이 0이면 간선이 존재하지 않는다는 뜻이다.

단, i = j인 경우에는 자기 자신으로 가는 거리이므로 최단 거리를 0으로 처리한다.

모든 정점 쌍 (i, j)에 대해 i번 정점에서 j번 정점으로 가는 최단 거리를 구하시오.

입력

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

두 번째 줄부터 N개의 줄에 걸쳐 인접 행렬 A가 주어진다.

출력

모든 정점 쌍 사이의 최단 거리를 N개의 줄에 걸쳐 출력한다.

i번 정점에서 j번 정점으로 갈 수 있다면 최단 거리를 출력하고, 갈 수 없다면 X를 출력한다.

각 줄에는 N개의 값을 공백으로 구분하여 출력한다.

제한

• 1 <= N <= 100
• 0 <= A[i][j] <= 10000
• i != j이고 A[i][j] = 0이면 i번 정점에서 j번 정점으로 가는 간선이 없다는 뜻이다.
• i = j인 경우 A[i][j] = 0이다.
• 모든 간선의 가중치는 양수이다.

예시 입력

3
0 2 0
0 0 3
0 0 0

예시 출력

0 2 5
X 0 3
X X 0