문제

당신은 유명한 미로 디자이너로, 크기의 미로를 만들어야 한다. 미로의 각 칸은 벽 혹은 공터로 이루어져 있으며 당신의 미로에 벽은 정확히 개 있어야 한다.

미로의 참가자는 미로의 임의의 공터에서 시작하여 상하좌우로 인접한 공터로 움직일 수 있다.

당신이 만든 미로는 해밀턴 경로를 보유하여야 한다. 해밀턴 경로란 미로의 모든 공터를 정확히 한번 지나는 경로를 말한다.

하지만 해밀턴 경로 문제는 NP-완전이기에 벚꽃컵이 채점할 수 있도록 해밀턴 경로도 직접 구해보자.

입력

첫째 줄에 , , 가 공백으로 구분되어 주어진다.

출력

개의 줄을 출력한다. 번째 () 줄에는 미로의 번째 행을 공백으로 구분하여 출력한다.

각 행은 개의 문자 혹은 수로 이루어져 있으며 번째 () 행의 번째 () 출력이 #이라면 해당 칸이 벽임을 의미한다.

만약 칸이 벽이 아니라면 그 칸은 공터이며 당신이 출력하는 해밀턴 경로에서 그 공터를 몇 번째로 방문하는지를 출력한다.

제약 조건

• 항상 주어진 입력에 대해 정답이 존재함을 증명할 수 있다.
• 입력으로 주어지는 모든 수는 정수이다.