스도쿠

스도쿠는 $9 \times 9$ 크기의 큰 격자를 $3 \times 3$ 크기의 작은 부분 격자 9개로 나눈 판에서 푸는 퍼즐입니다. 예를 들면 다음과 같습니다.

격자의 일부 칸에 숫자가 주어졌을 때, 남은 칸을 모두 채워서 $1$부터 $9$까지의 숫자가 다음 세 가지 조건을 모두 만족하도록 정확히 한 번씩 나타나게 하는 것이 목표입니다. (1) 9개의 $3 \times 3$ 부분 격자 각각, (2) 9개의 가로줄 각각, (3) 9개의 세로줄 각각.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 스도쿠 격자의 81개 칸을 위쪽 줄부터 한 줄씩 차례로 이어 붙인, 81개의 문자로 된 한 줄입니다. 각 문자는 숫자($1$부터 $9$까지)이거나, 아직 채워지지 않은 칸을 나타내는 마침표(.)입니다. 모든 퍼즐은 유일한 해를 가진다고 가정해도 됩니다. 입력의 끝은 end라는 단어만 있는 한 줄로 표시됩니다.

각 테스트 케이스마다 완성된 스도쿠 격자를 한 줄에 출력합니다. 완성된 격자는 위쪽 줄부터 차례대로 이어 붙인 81개의 숫자로 이루어지며, 마침표는 포함하지 않습니다.