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

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

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

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

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

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

입력

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

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

출력

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

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

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

제한

• \(1 \le N \le 100\)
• \(0 \le A[i][j] \le 10000\)
• \(i \neq 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