마지막 자리만

Jessie는 최근 조깅을 시작해서 피트니스 밴드로 진행 상황을 기록하고 있다. 근처 언덕에는 멋진 지점이 n개 있다. 아마추어 조깅을 하는 사람에게 오르막 달리기는 힘들기 때문에 Jessie는 내리막으로만 달릴 것이다. 지점에는 1부터 n까지 번호가 붙어 있고, 번호가 클수록 지점의 위치가 낮다. 어떤 지점 쌍은 산책로로 연결되어 있고, 여기서는 더 높은 지점에서 더 낮은 지점으로 가는 산책로 i → j만 고려한다 (i < j).

Jessie는 조깅을 여러 번 성공적으로 마쳤고, 연속한 두 지점 사이에 산책로가 있는 지점 순서를 각각 정확히 한 번씩 달렸다. 이제 Jessie는 피트니스 밴드가 수집한 데이터를 이용해 모든 산책로의 지도를 복원하려고 한다. 아쉽게도 밴드의 화면이 작아서, 1 ≤ i < j ≤ n인 각 지점 쌍 i, j 사이에서 Jessie가 달린 조깅 횟수의 마지막 자리만 보여줄 수 있다. 이 데이터를 바탕으로 Jessie가 언덕의 지도를 복원하도록 도와줄 수 있는가?

입력

입력의 첫째 줄에는 언덕의 지점 수 n이 주어진다 (2 ≤ n ≤ 500). 다음 n개의 줄이 주어지는데, i번째 줄에는 n개의 문자 ai,1, ai,2, . . . , ai,n이 있다. 문자 ai,j는 i번째 지점에서 시작해서 j번째 지점에서 끝나는 서로 다른 조깅의 횟수의 마지막 자리다. 모든 i ≥ j에 대해 ai,j = 0이다.

주어진 입력 데이터에 대해 답이 항상 존재함이 보장된다.

출력

n개의 줄을 출력해서 언덕의 지도를 비슷한 형식으로 나타내라. i번째 줄에는 n개의 문자가 있어야 하고, j번째 문자는 i번째 지점에서 j번째 지점으로 가는 산책로가 있으면 1, 없으면 0이다. 모든 i ≥ j에 대해 i번째 줄의 j번째 문자는 0이어야 한다.